DX's Digital Garden

8.乘积最大子数组(以数组下表

2 min read

  • 2.18
    • 好多小瑕疵，不知道是不是没睡够的原因
    • i 从 1 开始
    • 用全局参数保存最终结果

$maxF[i] = max(nums[i], nums[i] * maxF[i-1], nums[i] * minF[i-1]);$ $minF[i] = min(nums[i], nums[i] * maxF[i-1], nums[i] * minF[i-1]);$

  • 2.4
    • 两组参数，一组全局，一组临时存储上一组的全局参数
class Solution {
    public int maxProduct(int[] nums) {
        int Max = nums[0];
        int Min = nums[0];
        int ans=nums[0];
        for(int i=1;i<nums.length;i++){
            int currentMax = Max;
            int currentMin = Min;
            Max = Math.max(nums[i],Math.max(nums[i]*currentMax,nums[i]*currentMin));
            Min = Math.min(nums[i],Math.min(nums[i]*currentMax,nums[i]*currentMin));
            ans = Math.max(Max,ans);
 
        }
        return ans;
    }
}

  • 12.4

    • 这道题不用dp数组,用存储的上次的最大值最小值做dp[i-1],然后更新最大值最小值

  • 这里nums[i-1]是用lastMin保存

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxF = nums[0],minF = nums[0],ans = nums[0];
        for(int i=1;i<n;i++){
            int x = nums[i];
            int lastMax = maxF,lastMin = minF;
            maxF = Math.max(x,Math.max(x*lastMax,x*lastMin));
            minF = Math.min(x,Math.min(x*lastMax,x*lastMin));
            ans = Math.max(ans,maxF);
        }
        return ans;
    }
}
  • 这里的难点是负数会让最大值上下翻飞,所以同时存储最大值和最小值,不用dp数组

Graph View