Find the first and last indices of an array for which the sequential sum of elements from and to will be the largest

Question

I have an array of integers A [N]. I want to find indices n and m such that the sequential sum from the nth element to the mth is maximum. Search time is limited by the value of N.

It's my code:

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

I tried to insert these counters and each time the program didn't work correctly, and it is clear why. But, unfortunately, I don't know how to put them correctly (I hope you can fix it

Answer 1

This type of problem can be solved using Kadane's Algorithm and the complexity is linear.

The primary idea of this problem is to look for positive contiguous segments of the array. And finding the maximum sum among all positive contiguous segment. And also ignore segment that has negative sum (as we are intended to find the maximum sum).

Note: This idea will fail if all the values are negative. To fix this issues you can check if all the elements are negative or not and find the maximum value.

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