[Leetcode Solution] Maximum Product Subarray

Analysis 

• First idea came in mind is dynamic programming which would be fine if it is required to calculate the maximum sum subarray. However after short thinking it's easy to find out this is a greedy algorithm 
• Assume there is no Zero in the array, we can divide the problem into two sub problems
• If the number of negative elements in the array is even, the maximum product is multiple all the elements together
• If the number of negative elements in the array is odd, we calculate the two products of elements in which the first is from left to the last negative element and the second is from the first negative element to the last element. Then return the bigger one.
• Take zero element into consideration. If we multiple zero into product, the result is always equals to zero. So the solution is divide original array into multiple subarrays delimited by the zero. Then calculate the maximum product within each sub array. Last return the biggest one.

Note

Divide an array by given delimiter and perform calculation on each sub array. Code Template can be found here 
http://fmarss.blogspot.com/2014/10/divide-array-into-sub-arrays.html 

Code

[Leetcode Solution] Candy

Analysis

• My algorithm is greedy algorithm in O(nlogn) because sort is used. Better solution O(n)can be found here
• Sort the candy list in ascending order of rating
• Scan the candy list from the lowest node to highest node. 
• If the node is the biggest one among it, left adjacent node and right adjacent node, then set it candy number is 1. Otherwise if either side node's rating is smaller then its, set its candy number as the number of that node's plus 1

Note

• Define comparison function in C++
• Self defined function cmp. Note compare function cannot be a class method otherwise sort cannot invoke it

Code

Updated at LeetCode 2nd Pass