Kadenes算法用于最大子数组乘积问题。帮我找出代码中的错误。

huangapple go评论79阅读模式
英文:

Kadenes Algorithm for maximum product of subarray. Help me find the error in my code

问题

答案与预期不符。是 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


<details>
<summary>英文:</summary>

The answer is not expected.Does the for loop creating the error. The max value is not getting updated.I think it should get updated after every iteration but it doesnt seem to. 
Array has negative values
contagious subarray


    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&lt;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;  
    }
   }


Your input
[2,3,-2,4,-3]
Output
72
Expected
144

</details>


# 答案1
**得分**: 1

```java
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)); 
Here when calculating 'min' you are using the updated value of the 'max' in that iteration. But you should use value of previous iteration.

You can calculate max and store in 'temp' and after calculating 'min' you can update the 'max' to fix this.

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;
}

Output: '144'
英文:
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)); 

Here when calculating min you are using the updated value of the max in that iteration. But you should use value of previous iteration.

You can calculate max and store in temp and after calculating min you can update the max to fix this.

  public int maxProduct(int[] nums) {
    int gm = nums[0];
    int max = nums[0];
    int min = nums[0];
    
    for (int i = 1; i &lt; 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;
  }

Output: 144

huangapple
  • 本文由 发表于 2020年8月25日 23:50:59
  • 转载请务必保留本文链接:https://go.coder-hub.com/63582635.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定