Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Have you met this question in a real interview?

Yes

Example

For example, given the array[2,3,-2,4], the contiguous subarray[2,3]has the largest product =6.

line 20, lmax is updated in line 19, be careful

class Solution {

public:

/\*\*

 \* @param nums: a vector of integers

 \* @return: an integer

 \*/

int maxProduct\(vector<int>& nums\) {

    // write your code here

    if \(nums.empty\(\)\) {

        return -1;

    }

    int res = nums\[0\], lmin = nums\[0\], lmax = nums\[0\];

    for \(int i = 1; i < nums.size\(\); ++i\) {

        if \(nums\[i\] >= 0\) {

            lmax = max\(nums\[i\], nums\[i\] \* lmax\);

            lmin = min\(nums\[i\], nums\[i\] \* lmin\);

        } else {

            int temp = lmax;

            lmax = max\(nums\[i\], nums\[i\] \* lmin\);

            lmin = min\(nums\[i\], nums\[i\] \* temp\);

        }

        // cout << lmax << endl;

        res = max\(res, lmax\);

    }

    return res;

}

};