Maximum subarray problem

Problem Statement

Finding a contiguous sub-array which has the largest sum in an 1-D array.

Algorithm

This problem is solved by using Kadane Algorithm. This algorithm is a linear time algorithm.

Code in C++

C++ Kadane Algorithm

//Kadane Algorithm
//Finding the maximum subarray


#include <iostream>
#include <bits/stdc++.h>

using namespace std;
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int arr[]={5,-1,6,4,10,9,-60};
int maxi=0,ans=0;
int n=sizeof(arr)/sizeof(int);//number of elements in array
for(int i=0;i<n;i++){
maxi=max(0,maxi+arr[i]);
ans=max(maxi,ans);
}

cout<<"Maximum subarray sum is\t"<<ans<<endl;
return 0;
}

Output

monkeydluffy@onepiece:~$ g++ kadane.cpp
monkeydluffy@onepiece:~$ ./a.out
Maximum subarray sum is    33

Sources

Wikipedia-Maximum Sub-array Problem