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;
    }
};

5 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