数据结构与算法 动态规划

LeetCode-152.Maxinum Product Sbubarray(最大乘积子数组)

Posted by Lucky Xue on 2020-04-06

LeetCode - 152. Maximum Product Subarray(最大乘积子数组)

题目

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）。

示例 1:

1
2
3
4
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

示例 2:

1
2
3
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

如何快速求出所有以i位置结尾(nums[i])的子数组的最大累乘积?假设以nums[i-1]结尾的最大累乘积为maxEnds[i-1]，以nums[i-1]记为的最小累乘积为minEnds[i-1]，那么以nums[i]结尾的最大累乘积只有三种可能:

  • 可能是maxEnds[i-1] * nums[i]，这个是显然的，因为记录前面的最大值，如[3,4,5]；
  • 也可能是 minEnds[i-1] * nums[i]，因为minEnds[i-1]和nums[i]都有可能是负数，如[-2,-4]；
  • 也有可能是 nums[i]；

递归解法

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
private static int res;

public static int maxProduct1(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    res = nums[0];
    int last = maxMul(nums, nums.length - 1);
    res = Math.max(res, last);
    return res;
}

public static int maxMul(int[] arr, int i) {
    if (i == 0) {
        return arr[0];
    }
    int preMax = maxMul(arr, i - 1);
    int preMin = minMul(arr, i - 1);
    res = Math.max(res, preMax);
    return Math.max(preMax * arr[i], Math.max(preMin * arr[i], arr[i]));
}


public static int minMul(int[] arr, int i) {
    if (i == 0) {
        return arr[0];
    }
    int preMax =  maxMul(arr, i - 1);
    int preMin = minMul(arr, i - 1);
    return Math.min(preMin * arr[i], Math.min(preMax * arr[i], arr[i]));
}

递归加记忆解法

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
private static int res2;

private static int[] maxEnds;

private static int[] minEnds;

public static int maxProduct2(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    res2 = nums[0];
    maxEnds = new int[nums.length];
    Arrays.fill(maxEnds, Integer.MIN_VALUE);
    minEnds = new int[nums.length];
    Arrays.fill(minEnds, Integer.MAX_VALUE);
    int last = maxMul2(nums, nums.length - 1);
    res2 = Math.max(res2, last);
    return res2;
}

public static int maxMul2(int[] arr, int i) {
    if (i == 0) {
        return arr[0];
    }
    if (maxEnds[i] != Integer.MIN_VALUE) {
        return maxEnds[i];
    }
    int preMax = maxMul2(arr, i - 1);
    int preMin = minMul2(arr, i - 1);
    res2 = Math.max(res2, preMax);
    maxEnds[i] = Math.max(preMax * arr[i], Math.max(preMin * arr[i], arr[i]));
    return maxEnds[i];
}

public static int minMul2(int[] arr, int i) {
    if (i == 0) {
        return arr[0];
    }
    if (minEnds[i] != Integer.MAX_VALUE) {
        return minEnds[i];
    }
    int preMax = maxMul2(arr, i - 1);
    int preMin = minMul2(arr, i - 1);
    minEnds[i] = Math.min(preMin * arr[i], Math.min(preMax * arr[i], arr[i]));
    return minEnds[i];
}

动态规划解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int maxProduct3(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int[][] dp = new int[nums.length][2];
    int max = nums[0];
    dp[0][0] = nums[0];
    dp[0][1] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] >= 0) {
            // 正的最大值等于正的最大值乘以当前值
            dp[i][0] = Math.max(dp[i - 1][0] * nums[i], nums[i]);
            // 负的最大值等于负的最大值乘以当前值
            dp[i][1] = Math.min(dp[i - 1][1] * nums[i], nums[i]);
        } else {
            // 负的最大值等于正的最大值乘以当前值
            dp[i][1] = Math.min(dp[i - 1][0] * nums[i], nums[i]);
            // 正的最大值等于负的最大值乘以当前值
            dp[i][0] = Math.max(dp[i - 1][1] * nums[i], nums[i]);
        }
        max = Math.max(max, dp[i][0]);
    }
    return max;
}

滚动优化解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int maxProduct4(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int curMax = nums[0];
    int curMin = nums[0];
    int res = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int max = curMax * nums[i];
        int min = curMin * nums[i];
        curMax = Math.max(max, Math.max(min, nums[i]));
        curMin = Math.min(max, Math.min(min, nums[i]));
        res = Math.max(res, curMax);
    }
    return res;
}

关注【憨才好运】微信公众号，了解更多精彩内容⬇️⬇️⬇️

continuous_deployment
FEATURED TAGS
数据结构与算法 动态规划
FRIENDS