时间戳

首页 > 解决方案 > kadanes算法中的错误答案

c++ - kadanes算法中的错误答案

问题描述

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

标签： c++

解决方案

更改currmax= max(currmax, currmax+arr[i])为 currmax= max(arr[i], currmax+arr[i])as 以将当前值与数组值进行比较。

在您的情况下 -1, 4, 5
currmax 的值将更新如下：
1. currmax = -1, currmax+arr[1] = 3 (比较 btw(4,3))
2. currmax= 4 , currmax+ arr[2] = 9 (比较 btw(5,9))
3. 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)<<" ";
    }
}

推荐阅读