java - 子阵列最大乘积的 Kadenes 算法。帮我找出我的代码中的错误

Question

答案不是预期的。for 循环是否会产生错误。最大值没有更新。我认为它应该在每次迭代后更新，但似乎没有。数组有负值传染子数组

class Solution {
public int maxProduct(int[] nums) {
   int gm=nums[0];
    int max=nums[0];
    int min=nums[0];
    int lmax;
    int lmin;
    for(int i=1;i<nums.length;i++){
        max=Math.max(nums[i],Math.max(nums[i]*max,nums[i]*min));
        min=Math.min(nums[i],Math.min(nums[i]*min,nums[i]*max));            
        gm=Math.max(gm,Math.max(min,max));
        
        }
    
     return gm;  
}

}

您的输入 [2,3,-2,4,-3] 输出 72 预期 144

标签： java

Answer 1

max=Math.max(nums[i],Math.max(nums[i]*max,nums[i]*min));
min=Math.min(nums[i],Math.min(nums[i]*min,nums[i]*max)); 

在计算时，min您使用的是max该迭代中的更新值。但是您应该使用先前迭代的值。

您可以计算最大值并存储在temp计算后，min您可以更新max以解决此问题。

  public int maxProduct(int[] nums) {
    int gm = nums[0];
    int max = nums[0];
    int min = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
      int temp = Math.max(nums[i], Math.max(nums[i] * max, nums[i] * min));
      min = Math.min(nums[i], Math.min(nums[i] * min, nums[i] * max));
      max = temp;
      gm = Math.max(gm, Math.max(min, max));
    }
    return gm;
  }

输出：144