[leetCode152]乘积最大子数组

典型动态规划。

解题思路

1. 确定dp数组下标及含义： dp[i][0]表示以num[i]结尾的最大乘积，dp[i][1]表示以num[i]结尾的最小元素积；
2. 递推公式：
   • dp[i][0]=MAX(num[i],dp[i-1][0]*num[i],dp[i-1][1]*num[i])
   • dp[i][1]=MIN(num[i],dp[i-1][0]*num[i],dp[i-1][1]*num[i])
3. 确定遍历顺序：i的状态依赖于i-1，所以从前向后遍历
4. dp数组初始化：dp[0][0]=num[0],dp[0][1]=num[1];
5. 举例推导发现没有问题

代码

class Solution {
    public int maxProduct(int[] nums) {
        int[][] dp = new int[nums.length][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i][0] = Math.max(Math.max(nums[i], nums[i] * dp[i - 1][0]), nums[i] * dp[i - 1][1]);
            dp[i][1] = Math.min(Math.min(nums[i], nums[i]* dp[i - 1][0]), nums[i] * dp[i - 1][1]);
            max = Math.max(max, dp[i][0]);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14