leetcode-jecklee/MaximumProductSubarray.cpp at master · rainlee/leetcode-jecklee · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         God Bless Me     BUG Free Forever
*/
/***
 * 贪心
 * 记录i之前的连续最大乘积maxp和最小乘积minp（负数的情况）
 * 如果a[i] > 0, 则用maxp乘，并更新minp
 * 如果a[i] = 0, 则maxp minp 都取1
 * 如果a[i] < 0, 则用minp乘，并更新maxp
 * 注意a[i] = 0，时res跟0比，而不是maxp(1)
 ***/
class Solution {
public:
    int maxProduct(int A[], int n) {
        if (n < 1)
            return 0;

        int maxp = 1;
        int minp = 1;
        int res = A[0];
        for (int i = 0; i < n; ++i)
        {
            if (A[i] > 0)
            {
                maxp = max(maxp * A[i], A[i]);
                minp = min(minp * A[i], A[i]);
            }
            else if (A[i] < 0)
            {
                int tmp = maxp;
                maxp = max(minp * A[i], A[i]);
                minp = min(tmp * A[i], A[i]);
            }
            else  // 0
            {
                maxp = 1;
                minp = 1;
            }
            if (A[i])
                res = max(res, maxp);
            else
                res = max(res, A[i]);
        }
        return res;
    }
};