Code & Func

打卡，第9天

今天这道题做了好久。。。

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.

看到这道题，就让我想起了昨天做得那道Longest Substring Without Repeating Characters。

看起来很像是同一类的题目，想着用同一种方法去做，然后就考虑了好多奇奇怪怪的情况，最后代码写的及其混乱。

1
int maxProduct(vector<int>& nums) {
2
    int i = 0,j = 0;
3
    int ret = INT_MIN;
4
    int now = 0;
5

6
    for(j = 0;j < nums.size();j++){
7
        if (nums[j] == 0){
8
            while(now < 0 && i < j -1)
9
                now /= nums[i++];
10
            ret = max(ret,now);
11
            if (ret < 0) ret = 0;
12
            now = 0;
13
            i = j+1;
14
        } else {
15
            now = (now)?now*nums[j]:nums[j];
9 collapsed lines
16
            ret = max(ret,now);
17
        }
18
    }
19

20
    while(now < 0 && i < j - 1)
21
        now /= nums[i++];
22
    ret = max(ret,now);
23
    return ret;
24
}

这还是做完后进行了一些删减的答案，看起来很复杂，要我现在去解释它都有点困难。

先提提我的思路：

和昨天的一样，我用两个下标来标识当前Subarray,也就是说，然后让j不断向前去遍历。
我需要考虑的就是什么时候i向前，我的想法是：

当我们遇到一个0时，我们需要把i改成j+1,因为正常情况下Subarray中如果有个0，那么Subarray的乘积就必定是0，为什么说是正常情况呢，因为如果当前最大乘积小于0的话，那么我们遇到一个0，要把最大乘积改成0.
但是如果我们遇到这样的数组2 -1 4 0,我们当前的策略的返回值是2，但真正应该是4，因此另一个i向前的情况是：

遇到一个0或遍历完整个数组，我们需要让i向前移动，直到让当前乘积变成大于0，或者到达j。

最后将这一大段思路变成代码就成了我上面写的了，其实仔细想想，这些思路其实并不复杂，只是有点繁琐，如果心能静点的话，应该可以更快的AC掉这道题。

下面是dicuss中的方法：

1
int maxProduct(int A[], int n) {
2
    // store the result that is the max we have found so far
3
    int r = A[0];
4

5
    // imax/imin stores the max/min product of
6
    // subarray that ends with the current number A[i]
7
    for (int i = 1, imax = r, imin = r; i < n; i++) {
8
        // multiplied by a negative makes big number smaller, small number bigger
9
        // so we redefine the extremums by swapping them
10
        if (A[i] < 0)
11
            swap(imax, imin);
12

13
        // max/min product for the current number is either the current number itself
14
        // or the max/min by the previous number times the current one
15
        imax = max(A[i], imax * A[i]);
7 collapsed lines
16
        imin = min(A[i], imin * A[i]);
17

18
        // the newly computed max value is a candidate for our global result
19
        r = max(r, imax);
20
    }
21
    return r;
22
}

把注释去掉话，其实没几句话，说实话，第一次看没看懂，分析一下他的思路：

同样是遍历，但是它维护的不是下标，而是在A[0
]中的子数组的最大值imax和子数组最小值imin.
他用的是减治法，大概的想法是，我们知道A[0
]imax和imin，我们如果求出A[0
]的imax,imin。
- 如果A[n]>=0,那么imax = max(A[n],imax*A[n]);imin = min(A[n],imin*A[n])
- 如果A[n] < 0，那么imin = min(A[n],imax*A[n]);imax = max(A[n],imin*A[n])