casyup.me@outlook.com

0%

leetcode/152MaximumProductSubarray

Posted on

152 Maximum Product Subarray

找到数组中最大的连续乘积

my solution (8ms, 100%)

先将乘积以 0 为分界线分开, 这样得到的就是一段段最大的乘积(暂时无视正负)

而如果得到的数是负数, 那么分为 4 种情况

  1. 从左到右, 找到第一个负数, 用当前乘积除以它
  2. 从左到右, 找到第一个负数, 以该负数为界限, 获取左边的乘积
  3. 从右到左, 找到第一个负数, 用当前乘积除以它
  4. 从右到左,, 找到第一个负数, 以该负数为界限, 获取右边的乘积

这四种情况最大者, 视为这一段的最大值, 而所有这些段再做比较, 就得到了整个数组连续乘积的最大值

代码如下:

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
static const int _ = [] () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
} ();

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        size_t size = nums.size();
        if ( !size ) return 0;

        int b = 0;
        int e = size;
        int ret = nums[0];
        while (b < e) {
            int tb = b;
            while (b < e && nums[b] != 0) ++b;
            if (b - tb <= 1) {
                ret = max(ret, nums[tb]);
                if (b < e)
                    ret = max(ret, nums[b]);
                b += 1;
                continue;
            }

            int sum = 1;
            int tb2 = tb;
            while (tb2 < b) sum *= nums[tb2++];

            if (sum < 0) {
                int sumneg1 = 1;
                tb2 = tb;
                while (tb2 < b) { 
                    sumneg1 *= nums[tb2];
                    if (nums[tb2] < 0) break;
                    ++tb2;
                }
                int sum1 = sumneg1 / nums[tb2] == 1 ? sumneg1 : 
                    sumneg1 / nums[tb2];

                int sumneg2 = 1;
                tb2 = b - 1;
                while (tb2 >= tb) {
                    sumneg2 *= nums[tb2];
                    if (nums[tb2] < 0) break;
                    --tb2;
                }
                int sum2 = sumneg2 / nums[tb2] == 1 ? sumneg2 : 
                    sumneg2 / nums[tb2];

                sum /= max(sumneg1, sumneg2);
                sum = max(sum, sum1);
                sum = max(sum, sum2);
            }

            ret = max(ret, sum);
            b += 1;
        }

        return ret;
    }
};

不太满意, 代码有点过长了…

best solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len = nums.size();
        int max_num[len] = {0};
        int min_num[len] = {0};
        int max = nums[0];
        int min = nums[0];
        max_num[0] = nums[0];
        min_num[0] = nums[0];
        for (int i = 1; i < len; ++i) {
            int tmp1 = max_num[i-1] * nums[i];
            int tmp2 = min_num[i-1] * nums[i];
            int cur_max_num = tmp1 > tmp2 ? tmp1 : tmp2;
            int cur_min_num = tmp1 < tmp2 ? tmp1 : tmp2;
            max_num[i] = cur_max_num >= nums[i] ? cur_max_num : nums[i];
            min_num[i] = cur_min_num <= nums[i] ? cur_min_num : nums[i];
            max = max > max_num[i] ? max : max_num[i];
            min = min < min_num[i] ? min : min_num[i];
        }

        return max;
    }
};

啊. 简洁的小东西

不过, 我不是太懂这个代码的含义…

不过我觉得我的想法会好点, 虽然代码实现起来有点困难

但是它能一次性跳过很大一片区域, 对于连续整数很多的情况, 能够很快地计算出来

而这种的话会完完整整的遍历一次

emmm. 是的, 我觉得我的想法会好一点 :)