首页 > 代码库 > Maximum Product Subarray

Maximum Product Subarray

2024-08-03 15:33:36   224人阅读

The maximum product of sub-arrays in $[1, n]$ can be divided by 3 cases:

  1. A[n] is the maximum product of all sub-arrays in [1, n].
  2. The array which has the maximum product is end by A[n].
  3. The array of maximum product is not including A[n]. 

Thus the result can be expressed as 

result = max(case1, case2, case3)

The second situation is not normal. If A[n] is positive, it can be got by prePositiveMax[n-1], if A[n] is negative, it can be got by preNegativeMin[n-1].

 

So one brute method is: 

prePositiveMax[n] = max(prePositiveMax[n-1]*A[n], preNegativeMin[n-1]*A[n], A[n]); preNegativeMin[n] = min(prePositiveMax[n-1]*A[n], preNegativeMin[n-1]*A[n], A[n]);

 

A more accurate method is:  

We define pEnd[i]: the maximum non-negative product of subarray with A[i]

We define nEnd[i]: the minimum non-positive product of subarray with A[i]

 

In fact, here we use pEnd, nEnd intead of prePositiveMax, preNegativeMin, thus we have  

if(A[i] > 0){         pEnd[i] = max(A[i], pEnd[i-1]*A[i]);         nEnd[i] = nEnd[i] * A[i]; }else{         pEnd[i] = nEnd[i] * A[i];         nEnd[i] = min(A[i], pEnd[i]*A[i]); }

 

Then, we can simplify as  

if(A[i] < 0) swap(pEnd, nEnd);pEnd = max(pEnd*A[i], A[i]); nEnd = min(nEnd*A[i], A[i]);

 

So we conclude the whole code 

int maxProduct(int A[], int n) {    if(1 == n) return A[0];        int pEnd, nEnd, res;        pEnd = nEnd = res = 0;        for(int i = 0; i < n; ++i){        if(A[i] < 0) swap(&pEnd, &nEnd);                pEnd = max(pEnd*A[i], A[i]);        nEnd = min(nEnd*A[i], A[i]);                if(res < pEnd) res = pEnd; //from res = max(res, pEnd)    }        return res;}

 

The complete code is: 

class Solution {private:    int max(int a, int b){        return a > b ? a : b;    }    int min(int a, int b){        return a > b ? b : a;    }    void swap(int* a, int* b){        *a = *a + *b;        *b = *a - *b;        *a = *a - *b;    }    public:    int maxProduct(int A[], int n) {        if(1 == n) return A[0];                int pEnd, nEnd, res;                pEnd = nEnd = res = 0;                for(int i = 0; i < n; ++i){            if(A[i] < 0) swap(&pEnd, &nEnd);                        pEnd = max(pEnd*A[i], A[i]);            nEnd = min(nEnd*A[i], A[i]);                        if(res < pEnd) res = pEnd;        }                return res;            }};

 

 

 

 

Reference

  1. https://oj.leetcode.com/discuss/11852/share-c-code-with-dp-o-1-space-o-n-time
  2. http://www.ahathinking.com/archives/120.html

Maximum Product Subarray


联系
我们