英文:
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<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 < 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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论