CareerCup

/*
* This program is used to find the sum of contiguous subarray elements with largest sum
*/

package dynamic_prog.largest_cont_subarray;

public class MaximumSumSubarray {

	static void kadane_algo(int arr[]) {

		int max_sum_so_far = Integer.MIN_VALUE;
		int max_ending_here = 0;
		int n = arr.length;
		int i, low_index = 0, high_index = 0;
		int s = 0;

		for (i = 0; i < n; i++) {
			max_ending_here += arr[i];

			if (max_ending_here > max_sum_so_far) {
				max_sum_so_far = max_ending_here;
				low_index = s;
				high_index = i;
			}

			if (max_ending_here < 0) {
				max_ending_here = 0;
				s = i + 1;
			}
		}

		System.out.println("max_sum : " + max_sum_so_far + " from " + low_index
				+ " to " + high_index);
	}

	public static void main(String[] args) {
		kadane_algo(new int[] { 1, 3, -5, 15, 1, 11, -15, 18 });
	}
}

people.csail.mit.edu/bdean/6.046/dp/ (First link in this page) gives a great animated solution for this question.

Use Kadane's algorithm

public static int kadanes(int arr[]) {
		int currsum = 0, maxsum = 0;
		for (int i = 0; i < arr.length; i++) {
			currsum = currsum + arr[i];
				if (currsum > maxsum)
					maxsum = currsum;
					
				
			if (currsum < 0) 
				currsum = 0;
			
		}
		return maxsum;
	}

* This wont work for negative numbers

Isn't this the very famous and common largest sum subarray problem which is solved by DP in O(n) where n is the size of the array?

public class MaxSumConseqNosArray {
public static void main(String[] args) {

int max_ending_here = 0;
int max_so_far = 0;
int start = 1, end = 0;
int arr[] = { 5, 3, -20, 7, 9 };
for (int i = 0; i < arr.length; i++) {

max_ending_here = max_ending_here + arr[i];
if (max_ending_here < 0) {
max_ending_here = 0;
end = i;
}
/*
* Do not compare for all elements. Compare only when
* max_ending_here > 0
*/
if (max_so_far < max_ending_here) {
max_so_far = max_ending_here;
} else {

start = i;
}
System.out.println(max_so_far);

}
System.out.println(max_so_far);
System.out.println("strat: nad end: " + start + " " + end);
}

}

The subarray should be "15 1 11 -15 18" not "15 1 11".

Pseudo code

sum = 0, max = 0, start, end
a = 1,

for i = 1 to N
{
sum = sum + arr[i];

if (sum > max) {
max = sum;
end = i;
start = a;
}
if (sum < 0) {
a = i+1;
sum = 0;
}
}

The maximum sum subarray would be from arr[start] to arr[end]

public class Snippet<T> {
public static void main(String[] args) {
int[] input = { 1, 3, -5, 11, -1, 16, -15, 18 };
new Snippet().run(input);
}

private void run(int[] input) {
int max = Integer.MIN_VALUE, best0 = 0, bestN = 0;

for (int i = 0; i < input.length; i++) {
int cur = 0;
for (int j = i; j < input.length; j++) {
cur += input[j];
if (cur >= max) {
max = cur;
best0 = i;
bestN = j;
}
}
}
for (int i = best0; i <= bestN; i++) {
System.out.println(input[i]);
}
}
}

#include<iostream>

using namespace std;

void FindMaximumSubsequence(int * num,int N)
{
int I,J,maxI,maxJ,maxSum,currentSum;
I = J = 0;
maxI = maxJ = -1;
maxSum = currentSum = INT_MIN;

for(int i = 0; i < N; ++i)
{
if(currentSum <= 0 )
{
currentSum = num[i];
I = i;
J = i;
}
else
{
currentSum += num[i];
J = i;
}
if(currentSum >maxSum)
{
maxSum = currentSum;
maxJ = J;
maxI = I;
}
}
cout<<"\nMax I = "<<maxI;
cout<<"\nMax J = "<<maxJ;
}

int main()
{
int numarray[10] = {-10, -8, -11, -7,-9,-2,-1 ,-1, -8,-10};
FindMaximumSubsequence(numarray,10);
return 0;
}

First, the example should return 15 1 11 -15 18; the following code's time complexity is O(n)

private int maxSubarraySum(int[] dat){
if(dat == null || dat.length == 0) return 0;

int[] mem = new int[dat.length];
mem[0] = dat[0];

for(int i = 1; i < dat.length; i++){
mem[i] = (mem[i-1] >= 0 ? mem[i-1] : 0) + dat[i];
}

int ret = Integer.MIN_VALUE;

for(int i = 0; i < dat.length; i++){
ret = Math.max(ret,mem[i]);
}

return ret;
}

Why is "15, 1, 11" the answer and not "15, 1, 11, -15, 18", since it sums to 30 where as the provided soln sums to 27 only. This is the very famous dynamic problem, longest continuous sum problem, which can be done in O(n).

firstly the answer to ur input case should be 15, 1, 11, -15, 18 rather than 15, 1, 11.... since sum is 30 in former case,and 27 in later..
here is the C CODE,executed correctly on VISUAL STUDIO 2010
//wap to find set of consecutive items in a given array wid largest sum..
#include<stdio.h>
#include<conio.h>
int sum(int *,int,int);
int main()
{
int a[5];
int i=0,j=0,s1=0,s2=0,beg=0,end=0;
printf("enter the array elements \n");
for(i=0;i<5;i++)
scanf("%d",&a[i]);
s1=a[0];
printf("numbers u entered are.. \n");
for(i=0;i<5;i++)
printf("%d ",a[i]);
for(i=0;i<5;i++)
{
j=4;
while(j>=i)
{
s2=sum(a,i,j);
if(s2>s1)
{
s1=s2;
beg=i;
end=j;
}j--;

}
}
printf("numbers are... \n");
for(i=beg;i<=end;i++)
printf("%d ",a[i]);
getch();
}
int sum(int *a,int i,int j)
{
int s=0;
for(i;i<=j;i++)
s=s+a[i];
return s;
}

kadane's algo will give the right answer , and yes, output will be 15, 1, 11, -15, 18

#include <stdio.h>
#include <stdlib.h>


int main(){

int s,e,ts,te,i;
int sum,max;
int ar[100];
int len=8;



scanf("%d",&len);
for(i=0; i < len; i++)
scanf("%d ",ar+i);

max=0;
s=e=ts=0;
te=ts + 1;
sum = ar[ts] + ar[te];
while(te < len){
sum = sum + ar[te];
if(max < sum){
s = ts;
e = te;
max = sum;
te++;
}
else{
ts = te + 1;
te = ts + 1;
sum = ar[ts] + ar[te];
}
}

for(i=s;i<=e;i++)
printf("%d,",ar[i]);

return;
}

Hi All,
Here is variant of Kadane's algorithm which works for all negative numbers & a mix of +ve & -ve numbers too.

This code also helps you determine the sub-array with the largest sum.

public class SubArr {
	public static void main(String[] args) {

		int curr_sum = 0;
		int max_sum = 0;
		int start = 0, end = 0;
		int negMax = Integer.MIN_VALUE;
		int negMaxIdx = 0;
		boolean hasPositives = false;
		int arr[] = { -4,-15, -3, -20, 7, 9 };
		
		for (int i = 0; i < arr.length; i++) {

				curr_sum = curr_sum + arr[i];
				
				
				if(arr[i] >0){
					hasPositives = true;
				}
				if(arr[i]<0 && arr[i]>negMax && !hasPositives)
				{
					negMax=arr[i];
					negMaxIdx = i;
				}
				
				//If current sum tends to be -ve, reset the sum to 0 and update the start & end indexes to the next element
				if (curr_sum < 0) {
					curr_sum = 0;
					
					//dont increment the start & end ptrs beyond the array length 
					if(i+1 < arr.length)
						{
							end = i+1;
							start = i+1;
						}
				}
				
				/*
				 * Do not compare for all elements. Compare only when
				 * curr_sum > 0
				 */
				if (max_sum < curr_sum) {
					max_sum = curr_sum;
					end = i;
				}
				
				

		}
		
		if(!hasPositives)
		{
			System.out.println("- Max Sum == "+negMax);
			System.out.println("Sub Array indices == "+negMaxIdx+" To "+negMaxIdx);
		}
		else {
			System.out.println("Max Sum == "+max_sum);
			System.out.println("Sub Array indices == "+start+" To "+end);
		}
		
	}

}

#define SIZEOFARRAY 8
void main()
{
int a[SIZEOFARRAY]={ 1, 3, -5, 15, 1, 11, -15, 18};

int sum;
int maxSum;
int i;
int startingIndex = 0;
int endingIndex = 0;

sum = a[0];
maxSum = sum;

for ( i = 1; i < SIZEOFARRAY; i++)
{
if ( a[i] >= 0)
{
if( sum >= 0 )
{
sum = sum + a[i];
}
else
{
sum = a[i];
startingIndex = i;
}
}
else
{
if ( sum >= a[i] && sum >= 0 )
{
sum = sum + a[i];
}
else
{
sum = a[i];
startingIndex = i;
}

}

if ( sum > maxSum )
{
maxSum = sum;
endingIndex = i;
}
}

printf ( "printing maxSum = %d \n", maxSum);
printf ( "printing startingIndex = %d \n",startingIndex );
printf ( "printing endingIndex = %d \n", endingIndex);
if ( startingIndex < endingIndex )
{
printf("{");
for ( i = startingIndex; i <= endingIndex; i++)
{
printf(" %d ", a[i]);
}
printf("}\n");
}
else
{
printf("{");
printf(" %d ", a[endingIndex]);
printf("}\n");
}
}

public static int getMaxSum(int[] numbers){
		int maxSum = 0;
		int currentSum = 0;
		int endIndex =0,startIndex =0;
		for(int i=0;i<numbers.length;i++){
			if(currentSum == 0){
				startIndex = i;
			}
			currentSum += numbers[i];			
			if(maxSum < currentSum){
				maxSum = currentSum;
				endIndex = i;
			}else if(currentSum < 0){				
				currentSum = 0;
			}			
		}
		System.out.println("Start Index: "+startIndex + " End Index:" +endIndex);
		int[] maxSequence = new int[endIndex-startIndex];
		System.arraycopy(numbers, startIndex,maxSequence , 0, endIndex-startIndex);
		return maxSum;
    }