ronith
10/12/2018 - 9:03 AM

Kadane algorithm

Kadane’s Algorithm:

Initialize: max_so_far = 0 max_ending_here = 0

Loop for each element of the array (a) max_ending_here = max_ending_here + a[i] (b) if(max_ending_here < 0) max_ending_here = 0 (c) if(max_so_far < max_ending_here) max_so_far = max_ending_here return max_so_far

Kadane algorithm-indices.cpp
content_copyfile_download
#include <bits/stdc++.h>
using namespace std;

void maxSubarray(vector<int> arr) {
    long n= arr.size();

    //Kadane's algo for maxSubarray
    int m=arr[0],curr=arr[0], s=0, e=0, a,b;
    for (long i=1;i<n;i++) {
        if (arr[i]>curr+ arr[i]) {
            s=i;
            e=i;
            curr= arr[i];
        }
        else {
            e++;
            curr+= arr[i];
        }
        if (m<curr) {
            m= curr;
            a=s;
            b=e;
        }
    }
    cout<< m<<"\n";
    cout<< "Indices are :"<< a<< " "<<b;
}

int main() {
    int t;
    cin>>t;
    while(t-->0){
        long n;
        cin>>n;
        vector<int> arr(n);
        for (long i=0;i<n;i++)
            cin>>arr[i];

        maxSubarray(arr);
}
}
Kadane algorithm.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int> arr(n);
    for (int i=0;i<n;i++)
        cin>>arr[i];

    int maxi=arr[0],curr=arr[0];
    for (int i=1;i<n;i++) {
        curr= max(arr[i], curr+arr[i]);
        maxi= max(maxi,curr);
    }
    cout<< maxi;
}