c++ - 查找数组的第一个和最后一个索引，其中元素从和到的顺序总和最大

Question

我有一个整数数组 A [N]。我想找到索引 n 和 m，使得从第 n 个元素到第 m 个元素的顺序和最大。搜索时间受限于N的值。

这是我的代码:

    #include <iostream>
    #include <vector>
    using namespace std;

    int MaxSum(vector<int> &A){
    int N=A.size();
    int n=0;
    int m=0;
    int prev_max=A[0];
    int sol_max=A[0];
    for (int i=1; i<N; i++){
       prev_max=max(A[i], A[i]+prev_max);
       if (prev_max>=sol_max){
            sol_max=prev_max;
        }  
    }
    cout<<"m="<<m<<endl;
    cout<<"n="<<n<<endl;
 //   cout<<sol_max<<endl;
}

int main()
{
vector<int> a={{-2},{1},{-3},{4},{-1},{2},{1},{-5},{4}};//for example: n=3; m=6
 MaxSum(a);
}

我尝试插入这些计数器，但每次程序都无法正常运行，原因很清楚。但是，不幸的是，我不知道如何正确放置它们(我希望你能修复它

Answer 1

此类问题可以使用 Kadane's Algorithm 解决并且复杂度是线性的。

这个问题的主要思路是寻找数组的正连续段。并在所有正连续段中找到最大总和。并且也忽略具有负和的段(因为我们打算找到最大和)。

注意:如果所有的值都是负数，这个想法就会失败。要解决此问题，您可以检查所有元素是否为负数并找到最大值。

int MaxSum(vector<int>&A) {
    int n=0,m=0;
    int max_so_far=0,max_ending_here=0;
    int prevIndex = 0;
    for(int i=0;i<A.size();i++) {
        max_ending_here += A[i];
        if(max_ending_here > max_so_far) {
            max_so_far = max_ending_here;
            n = prevIndex;
            m = i;
        }
        if(max_ending_here < 0) {
            max_ending_here = 0;
            prevIndex=i+1;
            prevIndex=i+1;
        }
    }

    cout<<"n: "<<n<<endl;
    cout<<"m: "<<m<<endl;
}