CareerCup

Kadane's algorithm - Maximum Subarray Problem

search terms: Kadane / max subarray.

It's tricky to get the linear code correct.

It seems there is a mistake in the question --
{5,6,-4,3} = 0,1; {8,9,-6,0,3,9} = 1, 5
the first example looks correct, but the second one would be 0,5 not 1,5.
Sum(0-5) = 23
Sum(1-5) = 15.

Thanks to Anonymous for pointing out at error in my my original and to S.Abakumoff for pointing out that the original algorithm requires at least one positive number. This solution addresses both comments:

Kadane's algorithm is the go-to solution for the maximum subarray problem. It is an iterative solution which runs in O(n) time. It finds largest subarray at each index i of array A, starting at index zero and iterates through the entire array. By using the knowledge of the previous largest subarray in combination with the knowledge that a previous subarray's sum can only be increased with a positive number at the next contiguous index, we can find the maximum contiguous subarray of A.

Consider the integer array A of size n where A contains at least one positive number (I'll handle the case where it doesn't at the end). To do this, we need to track 2 things: the current maximum subarray's sum and the maximum subarray which ends at index i. We’ll call them overallMax and maxEndingHere, respectively.

For each index, we set maxEndingHere equal to A[i] + the previous index's maxEndingHere. If it's not positive, we reset maxEndingHere equal to 0. Finally, we compare the value of maxEndingHere with overallMax and take the larger of the two numbers for our new overallMax. Note that in the actual algorithm, we would want to keep track of the current set of indices representing the overallMax. We would also make sure that array was not empty.

Here is a simple example: {6,-10,12}
overallMax =0
maxEndingHere=0

Start
A[0]:
maxEndingHere =Math.max(0, maxEndingHere + A[0]) =Math.max(0, 0 + 6)=6
overallMax=Math.max(overallMax, maxEndingHere)=Math.max(0,6)=6

A[1]:
maxEndingHere =Math.max(0, maxEndingHere + A[1]) =Math.max(0,6-10)=0
overallMax=Math.max(overallMax, maxEndingHere)=Math.max(0,6)=6

A[2]:
maxEndingHere=Math.max(0, 0 + A[2])=Math.max(0,12)=12
overallMax=Math.max(overallMax, maxEndingHere)=Math.max(6,12)=12
End

In the scenario where there are all negative numbers, I believe we could temporarily make all the numbers positive and use Math.min instead of Math.max to achieve the same result.. Then, at the end, we could return all the numbers to negatives and find the sum of the values given by our negative numbers between the indices of our max subarray.

public static int[] findMaxSubArray(int[] array, int start, int end)
	{

		if(start == end)
			return new int[]{start, end, array[start]}; // starIndex, endIndex, and Maxsum

		int mid = (start + end)/2;

		int[] leftMaxSubarray = findMaxSubArray(array, start, mid);

		int[] rightMaxSubarray = findMaxSubArray(array, mid +1, end);

		int[] crossMaxSubarray = findCrossMaxSubArray(array, start, mid, end);


		return max(crossMaxSubarray, max(leftMaxSubarray, rightMaxSubarray));

	}


	public static int[] max(int[] array1, int[] array2)
	{
		if(array1[2] > array2[2])
			return array1;
		return array2;
	}

	public static int[] findCrossMaxSubArray(int[] array, int start, int mid, int end)
	{
		int maxSum = Integer.MIN_VALUE;

		int sum = 0;

		int leftMaxIndex = mid;

		for(int i = mid; i >= start; i--)
		{
			sum = sum + array[i];
			if(sum > maxSum)
			{
				maxSum = sum;
				leftMaxIndex = i;
			}
		}

		sum = 0;
		int maxSum2 = Integer.MIN_VALUE;

		int rightMaxIndex = mid;
		for(int i = mid +1; i <= end; i++)
		{
			sum = sum + array[i];
			if(sum > maxSum2)
			{
				maxSum2 = sum;
				rightMaxIndex = i;
			}
		}
		
		return new int[]{leftMaxIndex, rightMaxIndex, maxSum + maxSum2};
	}

Thought to share the questions that were asked to me in the phone interview. The questions were pretty simple.

#include<stdio.h>
#include<stdlib.h>
#define len 9
int maxs(int a[])
{
int maxcurrsum=0;
int maxsum=0;
int i=0;
int start_temp=0;
int start=0;
int end=0;
for(;i<len;i++)
{
maxcurrsum=maxcurrsum+a[i];

if(a[i]>maxcurrsum)
{
maxcurrsum=a[i];
start_temp=i;
}

if(maxcurrsum>maxsum)
{
maxsum=maxcurrsum;
start=start_temp;
end=i;
}
}
printf("%d %d\n",start,end);
for(i=start;i<end;i++)
printf("%d\n",a[i]);
return maxsum;
}

Also found in - jasmeetsingh.net/wordpress/?p=36

/*
 * Source: Wikipedia
 * 
 * In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
T
 */

package BST;

public class MaxSubArray {

	int arr[] = new int[]{-2, 1, -3, -4, -1, 2, 1, -5, 4};
	public MaxSubArray() {
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		int minPointer = 0;
		int maxPointer = 0;
		int subArrSum = 0;
		for(int i =0;i<arr.length;i++)
		{
			subArrSum += arr[i];
			if(subArrSum<min)
			{
				minPointer = i;
				min = subArrSum;
			}
			if (subArrSum>max)
			{
				maxPointer = i;
				max = subArrSum;
			}
				
		}
		minPointer++;
		if(minPointer >= maxPointer)
		{
			min = 0;
			minPointer = 0;
		}
		System.out.println(max - min);
		for(int i = minPointer; i<=maxPointer;i++)
		{
			System.out.print(arr[i] + " ");
		}
	}
}

Regarding jasmeet's answer: the 4th element in the array should be 4 and not -4 in order to match the wikipedia example

As I understand the Kadane's algorithm works only when the input array containing at least one positive number. The question does not tell anything about it..So I would start with clarifying..

Jasmeet`s algo won`t work if we have 4 instead of -4 and say -100 at the end of the array ... it`ll output -2, 1, -3, 4, -1, 2, 1 which is incorrect

public class algo1 {

static int arr[] = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4,-100};
public static void main(String args[]) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int minPointer = 0;
int maxPointer = 0;
int subArrSum = 0;
for(int i =0;i<arr.length;i++)
{
subArrSum += arr[i];
if(subArrSum<min)
{
minPointer = i;
min = subArrSum;
}
if (subArrSum>max)
{
maxPointer = i;
max = subArrSum;
}

}
minPointer++;
int sum2=0;
int flag=0;
if(minPointer >= maxPointer)
{
min=Integer.MAX_VALUE;
minPointer=0;
for(int i=0;i<maxPointer;i++)
{ sum2+=arr[i];
if(min>sum2) { min=sum2; minPointer=i;
}
flag=1;
}
}
//System.out.print(minPointer);
if(flag==1)
minPointer++;
//System.out.println(max - min);
for(int i = minPointer; i<=maxPointer;i++)
{
System.out.print(arr[i] + " ");
}
}
}


Tweak in jasmeet`s code .. instead of setting minptr to 0 if min>=max set it by finding the min. element just before the max element .

Python version:

def maximal_subarray(arr):
	if not arr:
		return []

	max_sum = arr[0]
	max_start = 0
	max_end = 0
	current_sum = arr[0]
	current_start = 0

	for i in range(1, len(arr)):
		current_sum += arr[i]

		if current_sum < arr[i]:
			current_sum = arr[i]
			current_start = i
		if current_sum > max_sum:
			max_sum = current_sum
			max_start = current_start
			max_end = i

	return arr[max_start:max_end+1]

#include<iostream>
using namespace std;
#include<conio.h>
int main()
{
          int i,s,*a,t=0,start=0,end=0,max_s=0,end1=0;
          cout<<"Enter size of first array";
          cin>>s;
          cout<<"Enter elements in first array:";
          a=new int[s];
          for(i=0;i<s;i++)
          cin>>a[i];
          for(i=0;i<s;i++)
          {
                  t=t+a[i];
                  if(t<a[i])
                  {
                            t=a[i];
                            start=i;
                            end=i;
                  }
                  else
                            end++;
                  if(t>max_s)
                  {
                             max_s=t;
                             end1=i;
                  }
          }
          cout<<"Max sum is:"<<max_s<<"\n";
          cout<<"start"<<start<<"\t"<<"end"<<end1;
          getch();
          return 0;
}

#include<iostream>
using namespace std;
#include<conio.h>
int main()
{
          int i,s,*a,t=0,start=0,end=0,max_s=0,end1=0;
          cout<<"Enter size of first array";
          cin>>s;
          cout<<"Enter elements in first array:";
          a=new int[s];
          for(i=0;i<s;i++)
          cin>>a[i];
          for(i=0;i<s;i++)
          {
                  t=t+a[i];
                  if(t<a[i])
                  {
                            t=a[i];
                            start=i;
                            end=i;
                  }
                  else
                            end++;
                  if(t>max_s)
                  {
                             max_s=t;
                             end1=i;
                  }
          }
          cout<<"Max sum is:"<<max_s<<"\n";
          cout<<"start"<<start<<"\t"<<"end"<<end1;
          getch();
          return 0;
}

This is called Maximum Subarray Problem.
If we want O(n) time complexity then we use Kadane's Algorithm.

//Kadane's Algorithm: O(n) time
function max_subarray(Array A){
	max_ending_here = max_so_far = 0;
	for (each x in array A) {
		max_ending_here = max(0, max_ending_here + x);
		max_so_far = max(max_so_far, max_ending_here);
	}
	return max_so_far;
}

Another solution (using divide and conquer) with O(n log n) time complexity exists.

//Divide and Conquer: O(n log n) time, (given in CLR book)
Given an array A. We want to find maximum continuous subarray. Divide the
array into two equal halves. The maximum subarray must lie in exactly one of
the following three places:
	1) entirely in the left half of the array A,
	2) entirely in the right half of the array A,
	3) crossing the midpoint of the array A
We can check the third possibility in linear time and we check first two
possibilities recursively.

//T(n) = 2T(n/2) + cn = O(n log n)

Cadene's Algo

Define M(t) such that
M(0) = 0, and

for each element in array Arr[t]           
	M(t) = max(0, M(t-1)+Arr[t])                 

find max element in array M. It will give you the maximum sub-array sum.

I tried with couple of examples and the below code snippet was giving correct result. It is not an elegant snippet though.

public static void main(String[] args) {
		// TODO Auto-generated method stub
		//int[] A = {8,9,-6,0,3,9}; //Maximum sum is: 23 of the elements from index 0 to 5
		//int[] A = {11, 12,-28,26}; //Maximum sum is: 26 of the elements from index 3 to 3
		int[] A = {11, 16,-28,31, -30, 31}; // Maximum sum is: 32 of the elements from index 3 to 5
		int sum = 0;
		int maxSum = 0;
		int indexIL = 0;
		int indexI = 0;
		int indexF = 0;
		for (int i = 0; i < A.length; i++) {
			sum += A[i];
			if(sum>maxSum){
				maxSum = sum;
				indexF = i;
				if(indexIL>indexI)
					indexI = indexIL;
			}
			if(sum<0){
				sum = 0;
				indexIL = i+1;
			}
		}
		System.out.println("Maximum sum is: "+ maxSum + " of the elements from index "+ indexI + " to "+ indexF );
	}

public class MaxSum
{

    public static void main(String a[])
    {
	MaxSum ms=new MaxSum();
	ms.maxSum();
    }
    void maxSum() {
	int[] arr = {25000,25000,900,3,7,188000,2600,120,24,89,123000};

	int leftPtr = 0;
	int leftPtrForMaxVal = 0;
	int rightPtr = arr.length-1;
	int rightPtrForMaxVal = 0;


	
	int j=arr.length-1;
	 leftPtrForMaxVal=arr[0];
	 rightPtrForMaxVal=arr[j];
	for(int i=0; i<arr.length-1;i++)
	{
	    if(arr[i]>leftPtrForMaxVal  && i!=rightPtr )
	    {
		leftPtrForMaxVal=arr[i];
		leftPtr=i;
	    }
	    if(arr[j]>rightPtrForMaxVal  && j!=leftPtr )
	    {
		rightPtrForMaxVal=arr[j];
		rightPtr=j;
	    }
	    j--;
	}
	
	
	   
	    System.out.println("leftPtrValue : "+leftPtrForMaxVal);
	    System.out.println("leftPtr : "+leftPtr);
	    System.out.println("rightRptValue : "+rightPtrForMaxVal);
	    System.out.println("rightPtr : "+rightPtr);

	

	
	
	}
}

int main()
{
int index1=0, index2=0, a;
int array1[12] = {1,2,3,4,5,6,8,7,10,4,1,2};
for(int i=0 ; i < sizeof(array1)/sizeof(int)-1 ; i++)
{
a = index1;
cout<<array1[index1]<<"index value one"<<endl;
cout<<array1[i]<<"i value"<<endl;
if(array1[index1]<array1[i+1])
{
index1 = i+1;
index2 = a;
}

}
system("pause");
return 0;
}

You should find the longest partial sequence that sums to the bigger number

//PseudoCode
	//if next is positive add it to part sum
	    //if partSum > maxSum make part the max, adjust indeces.
	//else if negative
	    //if (maxSum+value)>0
	        //if yes, we need it. Add it to the part sum.                
	        //else reset the index to this element+1 and make partsum =0;      
public class MaxPartSum {
	
	public PartSum findPartMaxSum(int[] arr){

	    int partSum =0;
	    int maxSum = 0;
	    int startIndex=0;
	    int endIndex =0;
	    
	    int i=0;
	    while (i<arr.length){
	        if (arr[i]>0)    //num is positive
	        {
	            partSum += arr[i];	//increase partSum
	            
	            if (partSum>maxSum){
	                maxSum = partSum;
	                endIndex = i;    
	            }
	        }
	        else{    //num is negative or zero
	            if (maxSum+arr[i] > 0)
	                partSum+=arr[i];
	            else    //the element doesn't help at all
	            {
	                partSum=0;
	                startIndex = i+1;
	            }
	        }      
	            
	        
	        i++;
	    }
	    System.out.println("Max Sum: " + maxSum);
	        System.out.println("Index " + startIndex + " to " + endIndex);
	    PartSum p = new PartSum(maxSum, startIndex, endIndex);
	    return p;
	}

	class PartSum{
	    int maxSum;
	    int startIndex;
	    int endIndex;
	    public PartSum(int maxSum, int startIndex, int endIndex){
	        this.maxSum = maxSum;
	        this.startIndex = startIndex;
	        this.endIndex = endIndex;
	    }
	}

	public static void main (String[] args){
		
		MaxPartSum m = new MaxPartSum();
		int[] arr = {-1, -2, 5, -2, -3};
		m.findPartMaxSum(arr);
	}
}

Java version of Kadane / max subarray:

public int[] indexRange(int[] array) {
    int beginTemp = 0;
    int begin = 0;
    int end = 0;
    int maxSoFar = array[0];
    int maxEndingHere = array[0];
    
    for (int i = 1; i < array.length; i++) {
        if (maxEndingHere < 0) {
            maxEndingHere = array[i];
            beginTemp = i;
        } else {
            maxEndingHere += array[i];
        }
         
        // calculate maxSoFar
        if(maxEndingHere >= maxSoFar) {
            maxSoFar  = maxEndingHere;
            begin = beginTemp;
            end = i;
        }
    }
    return new int[]{begin, end, maxSoFar};
}

We can use dynamic programming here.

findMaxSum(int index) {
	return Math.max(arr[index] + findMaxSum(index+1) , findMaxSum(index+1));
}

This is not the entire code just the idea. This will just give you the max sum. The logic can be tweaked to get the index.

Simpler and Easier to understand
#include<stdio.h>
int GetLargestSubArray(int* arr, int n){
int iBeginSaved=0, iEndSaved=0; // the start/end positions of the saved sub array
int iBegin=0, iEnd=0; // the start/end positions of the current sub array
int nSumSaved=0, nSum=0; // the sums of whole saved largest and current sub arrays
int i = 0; // index to loop in the array
if (0 == n){

iEndRet = iBeginRet = -1;
return 0;
}
nSumSaved = nSum = arr[i];
for(i = 1; i < n; i++) {
/* Compute the current largest sum */
if (nSum<=0){
nSum = arr[i];
iBegin = iEnd = i;
}
else{
nSum += arr[i];
iEnd = i;
}
if (nSum > nSumSaved){
nSumSaved = nSum;
iBeginSaved = iBegin;
iEndSaved = iEnd;
}}
printf("\n%d %d",iBeginSaved,iEndSaved);
return nSumSaved;
}
int main(){
int a[]={1, -9,4, 15, -9, 0, -6, 6, -12, 2, 3};
int n=sizeof(a)/sizeof(a[0]);
printf("%d ",n);
GetSubArray(a,n,0,0);
}

Generally, we have a left index and a right index indicating the boundaries of the current window. We also have a running sum of the current window. If the running sum goes below zero, then we start a new window from right+1. Update the maxSum accordingly. It works for both negative or positive arrays.

public class Pair
{
	public int first;
	public int second;
	
	public Pair(int f, int s)
	{
		first=f;
		second=s;
	}
	public String toString()
	{
		return String.format("[Pair: first=%d, second=%d]", first, second);
	}
}
public class ID5256786030362624
{
	public Pair maxSubarray(int[] A)
	{
		if (A==null || A.length==0)
			return null;
		Pair result=new Pair(-1, -1);
		int maxSum=Integer.MIN_VALUE;
		int left=0;
		int sum=0;
		for (int right=0; right<A.length; right++)
		{
			sum += A[right];
			if (sum>maxSum)
			{
				maxSum=sum;
				result.first=left;
				result.second=right;
			}
			if (sum<0)
			{
				sum=0;
				left=right+1;
			}
		}
		return result;
	}
	
	public static void main(String[] args)
	{
		int[] A={5,6,-4,3}; 
		int[] B={8,9,-6,0,3,9};
		int[] C={-1, -2, -5, -10};
		ID5256786030362624 wpd=new ID5256786030362624();
		System.out.println(wpd.maxSubarray(A));
		System.out.println(wpd.maxSubarray(B));
		System.out.println(wpd.maxSubarray(C));
	}
}

#include "stdafx.h"
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
	int testCase [] = { 8, 9, -6, 0, 3, 9 };
	queue<int> indexQueue;
	int descendingNum = 0;
	bool ascending = false;
	int ascendingFinalIndex = 0;
	int ascendingBeginIndex = 0;
	for (int i = 0; i < 6; i++)
	{
		if (testCase[i] < 0)
		{
			if (ascending)
			{
				ascending = false;
				ascendingFinalIndex = i - 1;
				descendingNum = testCase[i];
			}
			else
			{
				descendingNum += testCase[i];
			}
		}
		else
		{
			ascendingFinalIndex = i;
			if (!ascending)
			{
				if (descendingNum > 0)
				{
					ascending = true;
					descendingNum = 0;
					ascendingFinalIndex = i;
				}
			}
		}
	}
	cout << ascendingBeginIndex << "," << ascendingFinalIndex;
	system("pause");
	return 0;
}

#include "stdafx.h"
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
	int testCase [] = { 8, 9, -6, 0, 3, 9 };
	queue<int> indexQueue;
	int descendingNum = 0;
	bool ascending = false;
	int ascendingFinalIndex = 0;
	int ascendingBeginIndex = 0;
	for (int i = 0; i < 6; i++)
	{
		if (testCase[i] < 0)
		{
			if (ascending)
			{
				ascending = false;
				ascendingFinalIndex = i - 1;
				descendingNum = testCase[i];
			}
			else
			{
				descendingNum += testCase[i];
			}
		}
		else
		{
			ascendingFinalIndex = i;
			if (!ascending)
			{
				if (descendingNum > 0)
				{
					ascending = true;
					descendingNum = 0;
					ascendingFinalIndex = i;
				}
			}
		}
	}
	cout << ascendingBeginIndex << "," << ascendingFinalIndex;
	system("pause");
	return 0;
}

static void Main(string[] args) 
        {
            int[] arr = { 5, 3, 1, 9, 12 };
            // this should return 0, 3 as the indexes that will produce larger sum

            int Lindex = 0, Rindex = 1, sum = 0, maxSum = arr[Lindex] + arr[Rindex];
            int tmp = (arr[Lindex] > arr[Rindex]) ? Lindex : Rindex;
            for (int i = 1; i < arr.Length; i++)
            {
                tmp = (arr[Lindex] > arr[Rindex]) ? Lindex : Rindex;
                sum = arr[tmp] + arr[i];
                if (sum > maxSum)
                {
                    Lindex = tmp;
                    Rindex = i;
                    maxSum = sum;
                }
            }

            Console.WriteLine(Lindex + " , " + Rindex + " : " + maxSum);
        }

void Largest_Indices(int arr[],int size)
{
	int pos=0,pos1=1,i,j;
	i=pos;
	for(j=i+1;j<size;j++)
	{
		if(arr[pos]<arr[j])
		{
			pos1=pos;
			pos=j;
		}
		
		else if(arr[pos1]<arr[j])
		{
			pos1=j;
		}
	}
	printf("%d %d",pos,pos1);
}
void main()
{
	int arr[]={34,67,98,21,33,21,223,12};
	Largest_Indices(arr,(sizeof(arr)/sizeof(int)));
}

void Largest_Indices(int arr[],int size)
{
	int pos=0,pos1=1,i,j;
	i=pos;
	for(j=i+1;j<size;j++)
	{
		if(arr[pos]<arr[j])
		{
			pos1=pos;
			pos=j;
		}
		
		else if(arr[pos1]<arr[j])
		{
			pos1=j;
		}
	}
	printf("%d %d",pos,pos1);
}
void main()
{
	int arr[]={34,67,98,21,33,21,223,12};
	Largest_Indices(arr,(sizeof(arr)/sizeof(int)));
}

A = [int(x) for x in raw_input().split()]

maxsofarstart = 0
maxsofarend = 0
maxsofar = A[0]
sumsofar_start = 0
sumsofar = A[0]

for i in xrange(1,len(A)):
    if A[i] > sumsofar:
        if sumsofar > 0: #include sumsofar
            sumsofar += A[i]
        else: #remove sumsofar
            sumsofar_start = i
            sumsofar = A[i]
    else:
        sumsofar = sumsofar + A[i]

    if sumsofar > maxsofar:
        maxsofar = sumsofar
        maxsofarstart = sumsofar_start
        maxsofarend = i

print maxsofarstart, maxsofarend

check_max(int arr, int i, int j, int *p_sum)
{
if( sum(arr,i,j)> *p_sum) *p_sum = sum(arr,i,j);
if(j+1< arr.len()-1)
{ check_max(arr,i,j+1, p_sum);
check_max(arr,i+1,j+1,p_sum);
}
if(j>i) check_max(i+1,j,p_sum);
return;
}

public class maxSum {

public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] a = {8, -6, 8, -3};
//int[] a = {11, 12, -28, 26};
//int[] a = {8,9,-6,0,3,9};
int[] a = {11, 16,-28, 31, -30, 31};
int maxSumVal = 0;
int sum = 0;
int previous = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i<a.length; i++)
{
sum = sum + a[i];
if(sum > 0)
{
if(sum >= previous)
{
previous = sum;
maxSumVal = sum;
endIndex = i;
}

}
else
{
sum = 0;
startIndex = (i+1)%a.length;
}
}
System.out.println(maxSumVal);
System.out.println(startIndex);
System.out.println(endIndex);
}

}

public class maxSum {

public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] a = {8, -6, 8, -3};
//int[] a = {11, 12, -28, 26};
//int[] a = {8,9,-6,0,3,9};
int[] a = {11, 16,-28, 31, -30, 31};
int maxSumVal = 0;
int sum = 0;
int previous = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i<a.length; i++)
{
sum = sum + a[i];
if(sum > 0)
{
if(sum >= previous)
{
previous = sum;
maxSumVal = sum;
endIndex = i;
}

}
else
{
sum = 0;
startIndex = (i+1)%a.length;
}
}
System.out.println(maxSumVal);
System.out.println(startIndex);
System.out.println(endIndex);
}

}

#include<iostream>
#include<stdio.h>
#define MAX 5
int main(int argv,char**argc)
{
int index,index_start,index_end;
int end_index,sum=0,sum1=0;
end_index=MAX-1;
int array[MAX];
std::cout<<"Enter data"<<std::endl;
for(index=0; index<MAX; index++)
{
std::cin>>array[index];
}
for(index=0; index<MAX-2;)
{
if(index==end_index)
{
index++;
end_index=MAX-1;
}
sum=array[index]+array[end_index];
if(sum1<sum)
{
sum1=sum;
index_start=index;
index_end=end_index;
}
end_index--;
std::cout<<"loop"<<std::endl;
}
std::cout<<index_start<<","<<index_end<<std::endl<<"sum"<<sum1<<std::endl;
}

#include<iostream>
#include<stdio.h>
#include<malloc.h>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<string>
#include<stdlib.h>
#include<math.h>
#define SIZE sizeof(arr)/sizeof(int)
#define FEL(i,a,b) for(int i=a;i<b;i++)
#define INF 1<<30
using namespace std;
int main()
{
int arr[]={5,-6,-4,-3,9,-9};
int start = 0,end = 0 ,sum = 0;int reset =0;
for(int i=0;i<6;i++)
{
sum +=arr[i];
if(sum<0)
{
sum =0;reset =i+1;
}
if(sum - arr[i] < sum)
{
start = reset;
end= i;
sum =sum+arr[i];
}
if(sum ==0)
{
reset =i+1;
}
}
cout<<start<<end;
return 0;
}

public class MaxSum {

	
	public static void main(String[] args) {
		Integer []input = {3,4,-8,9};
		int loc1 = 0, loc2 = 0;
		int max = input[0];		
		for(int i=1; i<input.length; i++)
		{			
			if(max < input[i])
			{
				loc2 = loc1;
				loc1 = i;
				max = input[i];
			}					
		}
		if(loc1 == loc2)
			loc1++;
		System.out.println(loc2 + " "+loc1);

	}

}

I think this is a far simple code that what others have suggested.

Is it a dynamic programming problem?
if a[i]...a[j] is the max subsequence of a[0]...a[n]
and a[k]...a[n] is the max subsequence of a[0]...a[n] that ends with a[n]
value[n] = a[i] + a[i+1] + ... a[j]
start[n] = i
last[n] = j
value2[n] = a[k] + a[k+1] + ... + a[n]
start2[n] = k

value2[n+1] = max(value2[n]+a[n+1], a[n+1])
start2[n+1] = (value2[n]>0)?k,(n+1)
value[n+1] = max(value[n], value2[n+1])
start[n+1] = (value[n]>value2[n+1])?start[n], start2[n+1]
last[n+1] = (value[n]>value2[n+1])?last[n]，(n+1)

public class MaxSubArray {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] data = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
		int[] result = findMaxSubArray(data, 0, data.length-1);
		System.out.println(result[0] + " " + result[1] + " " + result[2]);
	}
	
	public static int[] findMaxCrossing(int[] A, int low, int mid, int high) {
		int left_sum = -1000;
		int left_index = 0;
		int sum = 0;
		for (int i = mid; i >= 0; i --) {
			sum += A[i];
			if (sum > left_sum) {
				left_sum = sum;
				left_index = i;
			}
		}
		
		int right_sum = -1000;
		int right_index = 0;
		sum = 0;
		for (int i = mid + 1; i < high; i++) {
			sum += A[i];
			if (sum > right_sum) {
				right_sum = sum;
				right_index = i;
			}
		}
		
		int[] result = {left_index, right_index, left_sum + right_sum};
		return result;
	}

	public static int[] findMaxSubArray(int[] A, int low, int high) {
		int[] result = new int[3];
		int[] resultLeft = new int[3];
		int[] resultRight = new int[3];
		int[] resultCross = new int[3];
		if (high == low) {
			result[0] = low;
			result[1] = high;
			result[2] = A[low];
			return result;
		} else {
			int mid = (int) Math.floor((low + high)/2);
			resultLeft = findMaxSubArray(A, low, mid);
			resultRight = findMaxSubArray(A, mid + 1, high);
			// (cross-low, cross-high, cross-sum) = findMaxCrossing(A, low, mid, high)
			resultCross = findMaxCrossing(A, low, mid, high);
			if (resultLeft[2] >= resultRight[2] && resultLeft[2] >= resultCross[2]) {
				return resultLeft;
			} else if (resultRight[2] >= resultLeft[2] && resultRight[2] >= resultCross[2]) {
				return resultRight;
			} else {
				return resultCross;
			}
		}
	}
}

public static int MaxSubArray(int[] arr){
        int maxSum=0;
        int sum=0;
        for (int i=0; i<arr.length; i++){    
            sum+=arr[i];
            if (sum<0)
                sum = 0;
            if (maxSum<sum)
                maxSum=sum;
        }
        return maxSum;
    }

public static int MaxSubArray(int[] arr){
        int maxSum=0;
        int sum=0;
        for (int i=0; i<arr.length; i++){    
            sum+=arr[i];
            if (sum<0)
                sum = 0;
            if (maxSum<sum)
                maxSum=sum;
        }
        return maxSum;
    }

Fully working Java code - handles all the cases

public class Solution {
    public int maxSubArray(int[] A) {
       	int i=0;
        int max=0;
        int sum =0;
        int flag = 0;
        
        for(i=0;i< A.length;i++){
            
            sum = sum + A[i];
            
          if(sum < 0) {
            
            int j=0; 
            if(A.length == 1)
             max = A[0];
            
            else { 
                     
            for(j=0;j< A.length;j++)
            {    
            	 if(A[j] > 0 ){
            	   flag = 0;
            	   break;
            	 }
            	 
            	 else flag = 1;
                } 
               if(flag == 1){
                  max = A[0]; 
                 for(j=0;j< A.length-1;j++) {  
                   if(A[j+1] >= max)
                     max = A[j+1];
            	  }
               } 
            	 else{
            		 sum= 0;
            		 
            		 
            	   } 
            	 }
                 
             }
             
        else if(sum > max){
              max = sum;
           }
        }
        
   return max;
     }
  }

{
int maxi = s =arr[0];
for(int i=1;i<n;i++){
s += arr[i];
if(s < arr[i]) s = arr[i];
if(s > maxi) maxi = s;
}
cout << maxi << endll;
}

int maxSubSeq(int arr[],int n)
{
    int maxi,s;
    maxi = s = arr[0];
    for(int i=1;i<n;i++){
        s += arr[i];
        if(s < arr[i]) s = arr[i];
        if(s > maxi) maxi = s;
    }
    return maxi;
}

This is in Java:

public int MaxSubSequence(int[] numbers)
	{
		int maxUntilNow = 0;
		int maxSum = 0;
		for (int =0; i < numbers.lenght; i++)
		{
			maxUntilNow = maxUntilNow  + numbers[i];
			if (maxUntilNow < 0)
				maxUntilNow  = 0;
			if (maxSum < maxUntilNow )
				maxSum = maxUntilNow;

			return maxSum;
		} 
	}

onestopinterviewprep.blogspot.com/2014/03/namespace-arrayproblem-write-function.html

can be done in o(n) using kadane's algorithm

public int max ContiguousSum(int[] a){
int sum[] = new int[a.length];
sum[0] = a[0];
int max = 0;

for(int i=1; i<a.length;i++){
sum[i] = Math.max(sum[i-1]+a[i], a[i]);

if(max < sum[i]) {
max = sum[i]
}
}
return max;
}

int a[] = {-2, 11, -4, 13, -5, -2};
        int b[] = new int[a.length];
        b[0] = 0;
        int currentSum = a[0];
        int sum =a[0];
        int max = Integer.MIN_VALUE;
        for(int i = 1; i<b.length; i++){
            if(sum +a[i] > 0) sum += a[i];
            currentSum = Math.max(currentSum + a[i], a[i]);
            if(currentSum > max){
                sum = 0;
                max = currentSum;
            }
        }
        System.out.println(max);

int a[] = {-3, -2, 11, -4, 13, -5, -2};
        int sum;
        int currentSum =a[0];
        int max = Integer.MIN_VALUE;
        for(int i = 1; i<a.length; i++){
            sum = Math.max(currentSum + a[i], a[i]);
            if(sum > max){
                currentSum = 0;
                max = sum;
            }
            if(currentSum +a[i] > 0) currentSum += a[i];

        }
        System.out.println(max);

private static int[] getMaxSubArray(int[] array) {
        int max = array[0];
        int maxSoFar = max;
        int maxSoFarBegin = 0;
        int maxSoFarEnd = 0;
        for (int i = 1; i < array.length; i++) {
            max = Math.max(array[i], max + array[i]);


            maxSoFar = Math.max(maxSoFar, max);
            if (maxSoFar == max) {
                maxSoFarEnd = i;
                if (max == array[i]) {
                    maxSoFarBegin = i;
                }
            }
        }
        return new int[]{maxSoFarBegin, maxSoFarEnd, maxSoFar, aaa(array)};
    }

The key point is to add the values in the contiguous sub array until it's negative, otherwise keep adding. Here is the O(n) solution

public static int maxContinousSub(int []A) {
	int maxsub = 0;
	int maxsum = 0;

	for (int i = 0; i < A.length; i++) {
		maxsub = Math.max(maxsub+A[i], 0);

		maxsum = Math.max(maxsub, maxsum);
	}

	return maxsum;
}

// O(n^2)
}}}
int tab[] = {-2, 11, -4, 13, -5, -2};
const int size = sizeof(tab)/sizeof(tab[0]);
int max= -1;
int sum = 0;

for(int k=0;k<size;++k)
{
for(int z=k;z<size;++z)
{
sum += tab[z];
if(sum>max && z>k) max = sum;
}
sum = 0;
}
}}}

void maxSum(String[] args) {
int[] arr = {5,2,9,3,7,18,2,12};

int leftPtr = 0;
int leftPtrForMaxVal = 0;
int rightPtr = arr.length-1;
int rightPtrForMaxVal = 0;

while(leftPtr<rightPtr){
if(arr[leftPtr]>arr[leftPtrForMaxVal]){
leftPtrForMaxVal = leftPtr;
}
leftPtr++;

if(arr[rightPtr]>arr[rightPtrForMaxVal]){
rightPtrForMaxVal = rightPtr;
}
rightPtr--;
}

System.out.println("leftPtr : "+leftPtrForMaxVal);
System.out.println("rightRpt : "+rightPtrForMaxVal);

System.out.println("leftMax : " +arr[leftPtrForMaxVal]);
System.out.println("rightMax : "+arr[rightPtrForMaxVal]);
}

array is a[],
int max1=a[0],max2,t1=0,t2=0;
for(i=0;i<=max;i+++)
{
if(max1<=a[i])
max1=a[i];
t1=i;
max2=max1;
t2=t1;
}
printf("%d,%d",t1,t2);

index(int a[])
	{
		int p=0,q=1;
		for(int i=2;i<a.length;i++)
		{
			if(a[p]<a[i] && a[q]<a[i])
			{
				if(a[p]<a[q])
				p=i;
				else q=i;
			}
			else if (a[p]<a[i] && a[i]<a[q])
			p=i;
			else if (a[q]<a[i] && a[i]<a[p])
			q=i;
		}
		System.out.println("indices are "+p+" "+q);
	}

#include <iostream>

using namespace std;

int maxsum(int array[], int nlength)
{
	int nfirst;
	int nsecond;
	if(array[0] > array[1])
	{
		nfirst = array[0];
		nsecond = array[1];
	}
	else
	{
		nfirst = array[1];
		nsecond = array[0];
	}
	
	for(int i=2; i<nlength; i++)
	{
		if(array[i] >= nfirst)
		{
			nsecond = nfirst;
			nfirst = array[i];
		}
	}

	return nfirst + nsecond;
}

int main()
{
	int a[6] = {8,9,-6,0,3,9};
	cout<<maxsum(a,6)<<endl;
	
	return 0;
}

This can be solved by finding the max element in the array and second max in the array and by noting their index simulatneously.Naturally the summation of max and the second max give the max sum!This can be done in just 1 for loop over the array to find the max and second max

Finding firstLargest and second largest element

public static void rangeHL(int [] arr){
		int firstLargestIndex=0;
		int secondlargestIndex=0;
		
		for(int i=0;i<arr.length;i++){
			if(arr[i]>arr[firstLargestIndex]){
				secondlargestIndex=firstLargestIndex;
				firstLargestIndex=i;
			}else if(arr[i]>arr[secondlargestIndex]){
				secondlargestIndex=i;
			}
		}
	}

Here is the working solution..

public static void FindStartAndEndIndexesYeildingMaxSum(int[] array)
        {
            //Get the first two elements into two variables
            int secondLargeNumber = array[1];
            int firstLargeNumber = array[0];
            int startIndex = 0;
            int endIndex = 1;
            //start the loop from the third element
            for (int i = 2; i < array.Length; i++)
            {
                //if the first element is less than the current element in the array, copy the current element to first element
                if (firstLargeNumber <= array[i])
                {
                    //Before copying the current element into first element, verify if first element is greater than second element..if it is copy that to second element
                    if (firstLargeNumber > secondLargeNumber)
                    {
                        secondLargeNumber = firstLargeNumber;
                        endIndex = startIndex;
                    }

                    firstLargeNumber = array[i];
                    startIndex = i;
                }
                else
                {
                    //if first element is greater than current element,then check if current element is greater than the second element, if it is copy that to second element
                    if (array[i] > secondLargeNumber)
                    {
                        secondLargeNumber = array[i];
                        endIndex = i;
                    }
                }
            }
            Console.WriteLine(String.Format("Start Index is {0} and End Index is {1} and the Sum is {2}",startIndex,endIndex,firstLargeNumber+secondLargeNumber));
            Console.ReadLine();

}

Here is an implementation of Kadane's algorithm. It also handles the case where all numbers are negative.

public class MaximumSubarray {

	static int arr[] = {8,9,-6,0,3,9} ;


	public static void main(String args[]) {

		int curr_max = arr[0];
		int max_so_far = arr[0];
		int index_i = 0;
		int index_j = 0;

		for (int i=1; i<arr.length; i++) {

			if (arr[i] > curr_max + arr[i]) {
				index_i = i;
			}
			curr_max = Math.max(arr[i], curr_max + arr[i]);

			if (curr_max > max_so_far) {
				index_j = i;
			}
			max_so_far = Math.max(curr_max, max_so_far);

		}

		System.out.println(max_so_far);
		System.out.println(index_i);
		System.out.println(index_j);
	}

}

#include<iostream>
#include<vector>

using namespace std;
int find(vector<int> v)
{
int l = v.size();
int a[l][l];
for(int i = 0; i < l; i++){
a[i][i] = v[i];
}
for(int i = 0; i < l; i++){
for(int j = i + 1; j < l; j++){
a[i][j] = a[i][j - 1]+v[j];
}
}
int max = 0;
for(int i = 0; i < l; i++){
for(int j = i; j < l; j++){
if(max < a[i][j]){
max = a[i][j];
}
}
}

return max;
}

int main()
{
vector<int> v;
int n, k;
cin >> n;
for(int i = 0; i < n; i++){
cin >> k;
v.push_back(k);
}

cout << find(v) << endl;
return 0;
}

#include<iostream>
#include<vector>

using namespace std;
int find(vector<int> v)
{
	int l = v.size();
	int a[l][l];
	for(int i = 0; i < l; i++){
		a[i][i] = v[i];
	}
	for(int i = 0; i < l; i++){
		for(int j = i + 1; j < l; j++){
			a[i][j] = a[i][j - 1]+v[j];
		}
	}
	int max = 0;
	for(int i = 0; i < l; i++){
		for(int j = i; j < l; j++){
			if(max < a[i][j]){
				max = a[i][j];
			}
		}
	}
	
	return max;
}

int main()
{
	vector<int> v;
	int n, k;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> k;
		v.push_back(k);
	}

	cout << find(v) << endl;
	return 0;
}