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 };