Sunday, November 23, 2014

[LeetCode] Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

思路:

Maximum Subarray那题的变种。由于正负得负,负负得正的关系。以A[i]结尾的max product subarray同时取决于以A[i-1]结尾的max / min product subarray以及A[i]本身。因此,对每个i,需要记录min/max product两个状态:

max_product[i] = max(max_product[i-1]*A[i], min_product[i-1]*A[i], A[i]) 
min_product[i] = min(max_product[i-1]*A[i], min_product[i-1]*A[i], A[i]) 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxProduct(int A[], int n) {
        if(n<=0) return 0;
        int ret, curMax, curMin;
        ret = curMax = curMin = A[0];
        for(int i=1; i<n; i++) {
            int temp = curMax;
            curMax = max(max(curMax*A[i], curMin*A[i]),A[i]);
            curMin = min(min(temp*A[i], curMin*A[i]),A[i]);
            ret = max(ret, curMax);
        }
        return ret;
    }
};

6 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. curMin不应该和上一步的curMin再比较一下吗?

    ReplyDelete
    Replies
    1. 不需要。ln 10里已经包括了最小乘积比较。

      Delete
  3. how to find the starting index and ending index.

    ReplyDelete
  4. why cannot replace "ret = A[0]" with "ret = INT_MIN" ?

    ReplyDelete