Leetcode | Maximum Product Subarray

Leetcode 加新题了

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.

整理思路不难，就是维护一个包含当前位置的最大正数和最小负数。在处理负数的时候需要注意。

 1 class Solution {
 2 public:
 3     int maxProduct(int arr[], int n) {
 4         if (n <= 0) return 0;
 5         int maxPos = 1, minNeg = 1, max = INT_MIN;
 6         for (int i = 0; i < n; ++i) {
 7             if (arr[i] > 0) {
 8                 maxPos = maxPos * arr[i];
 9                 minNeg = minNeg > 0 ? 1: minNeg * arr[i];
10                 if (maxPos > max) max = maxPos;
11             } else if (arr[i] == 0) {
12                 maxPos = minNeg = 1;
13                 if (max < 0) max = 0;
14             } else { // arr[i] < 0
15                 int tmp = maxPos;
16                 if (minNeg > 0) {
17                     maxPos = 1;
18                 } else {
19                     maxPos = minNeg * arr[i];
20                     if (maxPos > max) max = maxPos;
21                 }
22                 minNeg = tmp * arr[i];
23                 if (minNeg > max) max = minNeg;
24             }
25         }
26         return max;
27     }
28 };

看了一下solution之后，还有更简洁的写法。我还是好弱。每天都能学到新东西啊。

 1 class Solution {
 2 public:
 3     int maxProduct(int arr[], int n) {
 4         if (n <= 0) return 0;
 5         int maxSoFar = arr[0], minSoFar = arr[0], ans = arr[0];
 6         for (int i = 1; i < n; ++i) {
 7             int tmp = maxSoFar;
 8             maxSoFar = max(max(arr[i], maxSoFar * arr[i]), minSoFar * arr[i]);
 9             minSoFar = min(min(arr[i], tmp * arr[i]), minSoFar * arr[i]);
10             if (maxSoFar > ans) ans = maxSoFar;
11         }
12         return ans;
13     }
14 };