kadanes算法中的错误答案
kadanes算法中的错误答案
提问于 2018-06-08 12:24:16
kadane的算法实现input = (t=1;n=3;arr={-1,4,5})给出输出8，但期望输出为9。
#include <iostream>
#include<cmath>
using namespace std;
int Max( int *arr, int n){
int currmax = arr[0];
int globalmax = arr[0];
for(int i = 1; i < n; i++) {
currmax= max(currmax, currmax + arr[i]);
if(currmax > globalmax)
globalmax = currmax;
}
return globalmax;
}
int main() {
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++) cin >> arr[i];
cout << Max(arr, n) << " ";
}
}回答 2
Stack Overflow用户
回答已采纳
发布于 2018-06-08 12:35:29
将currmax= max(currmax, currmax+arr[i])更改为currmax= max(arr[i], currmax+arr[i])，以比较当前值和数组值。
在你的案例中-1，4，5
currmax的值将按以下方式更新：
- currmax = -1，currmax+arr1 =3(比较btw(4,3))
- currmax= 4，currmax+arr2 =9(比较btw(5,9))
- currmax =9 代码如下：
#include <iostream>
#include <cmath>
using namespace std;
int Max( int *arr, int n){
int currmax=arr[0];
int globalmax=arr[0];
for(int i=1;i<n;i++) {
currmax= max(arr[i], currmax+arr[i]); // your code line was wrong here check and try
if(currmax>globalmax)
globalmax=currmax;
}
return globalmax;
}
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++) cin>>arr[i];
cout<<Max(arr,n)<<" ";
}
}Stack Overflow用户
发布于 2022-10-02 07:02:08
请找到最大SubArray的正确答案(卡达内定理)
C#解决方案：
public int MaxSubArray(int[] nums) {
int maxSum = nums[0];
int currSum = 0;
for(int i = 0; i < nums.Length; i++){
currSum = currSum + nums[i];
if(maxSum < currSum){
maxSum = currSum;
}
if(currSum < 0){
currSum = 0;
}
}
return maxSum;
}
enter code here页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50760610
复制相关文章
相似问题
腾讯云开发者
