首页 > 代码库 > LeetCode Maximum Product Subarray

LeetCode Maximum Product Subarray

class Solution {public:    int maxProduct(int A[], int n) {        if (A == NULL || n < 1) {            return INT_MIN;        }        int res = INT_MIN;        int tr = 1;        for (int i=0; i<n; i++) {            tr = tr * A[i];            if (tr > res) {                res = tr;            }            if (tr == 0) {                tr = 1;            }        }        tr = 1;        for (int i=n-1; i>=0; i--) {            tr = tr * A[i];            if (tr > res) {                res = tr;            }            if (tr == 0) {                tr = 1;            }        }        return res;    }};

 更叼的方法,不过速度上没有明显提升

class Solution {public:    int maxProduct(int A[], int n) {        // store the result that is the max we have found so far        int r = A[0];            // imax/imin stores the max/min product of        // subarray that ends with the current number A[i]        for (int i = 1, imax = r, imin = r; i < n; i++) {            // multiplied by a negative makes big number smaller, small number bigger            // so we redefine the extremums by swapping them            if (A[i] < 0)                swap(imax, imin);                // max/min product for the current number is either the current number itself            // or the max/min by the previous number times the current one            imax = max(A[i], imax * A[i]);            imin = min(A[i], imin * A[i]);                // the newly computed max value is a candidate for our global result            r = max(r, imax);        }        return r;    }};

 

LeetCode Maximum Product Subarray