Code & Fun

打卡,第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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int maxProduct(vector<int>& nums) {
int i = 0,j = 0;
int ret = INT_MIN;
int now = 0;

for(j = 0;j < nums.size();j++){
if (nums[j] == 0){
while(now < 0 && i < j -1)
now /= nums[i++];
ret = max(ret,now);
if (ret < 0) ret = 0;
now = 0;
i = j+1;
} else {
now = (now)?now*nums[j]:nums[j];
ret = max(ret,now);
}
}

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

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

先提提我的思路:

  • 和昨天的一样,我用两个下标来标识当前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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

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

  • 同样是遍历,但是它维护的不是下标,而是在A[0:j]中的子数组的最大值imax和子数组最小值imin.

  • 他用的是减治法,大概的想法是,我们知道A[0:n-1]imax和imin,我们如果求出A[0:n]的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])

本文首发于Code & Fun