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

Laura 发表于 Dev

劳拉

我有一个整数数组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);
}

我试图插入这些计数器，并且每次程序运行不正常时，原因很明显。但是，不幸的是，我不知道如何正确放置它们（希望您可以修复它

Al Mamun Akash

可以使用Kadane算法来解决这类问题，并且复杂度是线性的。

这个问题的主要思想是寻找阵列的正连续段。并在所有正连续段中找到最大和。并且也忽略具有负和的段（因为我们打算找到最大和）。

注意：如果所有值均为负，则此方法将失败。要解决此问题，您可以检查所有元素是否为负数并找到最大值。

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

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。