CareerCup

http://en.wikipedia.org/wiki/Kadane%27s_Algorithm

Explains the solution, which solves in O(n) time.

int MaxSubArray(int *a, int size, int &from, int &to)
{
int sum = 0, maxSum = 0;
for (int i = 0; i < size; ++i) {
sum += a[i];
if (sum >maxSum) {
to = i; // RANGE OF MAXIMUM SUB ARRAY TILL THIS POSITION
maxSum = sum;
}
else if (sum < 0) {
from = i+1; // RANGE OF MAXIMUM SUB ARRAY STARTS FROM THIS POSITION.
sum = 0;
}
}
return maxSum;
}

cant get better than this one... this is the best... i tried it

public final class MaxSumTest
{
static private int seqStart = 0;
static private int seqEnd = -1;

public static int maxSubSum3( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;

for( int i = 0, j = 0; j < a.length; j++ )
{
thisSum += a[ j ];

if( thisSum > maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
else if( thisSum < 0 )
{
i = j + 1;
thisSum = 0;
}
}

return maxSum;
}
public static void main( String [ ] args )
{
int a[ ] = { 4, -3, 5, -2, -1, 2, 6, -2 };
int maxSum;


maxSum = maxSubSum3( a );
System.out.println( "Max sum is " + maxSum + "; it goes"
+ " from " + seqStart + " to " + seqEnd );

}
}

Can you give more explanation or example?

Array: consecutive memory locations
sub_array: size less than original array (atleast one less)
+ Find all possible sub arrays within the given array
+ Compute the sum of each possible sub array
+ Find the max among the sum of all subarrays

If the array was filled with both positive and negative nos, then we have to compute the sum of all possible subarrays. One way to look at this is to collect all subarray sums from each position.

Ex 1: 3 7 1 8 4

3
3 7
3 7 1
3 7 1 8

7
7 1
7 1 8
7 1 8 4

1
1 8
1 8 4

8 
8 4

4

So, to add code to do the above, leads us to:

max_sum=0;
max_sum_start_pos=0;
max_sum_end_pos = 0;

for(i=0; i<n; i++) {
	sum[i] = 0
	end = (i==0)?(n-1):(n);

	for (j=i; j<end; j++) {		            
		sum += a[j];
		if (sum > max_sum) {	
			max_sum = sum;
			max_sum_start_pos = i;		
			max_sum_end_pos = j;		
		}
	}	
}

Obviously, the abobe algorithm is O(n^2). The minimum time possible is O(n) as all the elements have to be visited atleast once. So, the next step is to come up with an algorithm that is O(n).

This problem is explored in great detail in programming pearls.. sure there is a linear solution and I guess K2G's solution can be refined to get the correct program

This problem is explored in great detail in programming pearls.. sure there is a linear solution and I guess K2G's solution can be refined to get the correct program

Maximum sum of the sub array can be done in number of ways depending on the time complexity needed, the space constraint and preprocessing allowed.

It can be done in a straight forward way by adding the positive numbers as you see them. Then once you see a negative number, start adding the negative numbers and store the positive number as temp_max. At the end of the negative number run,see if the sum of negative number hurts or adds to the temp_max. If it hurts, exclude the negative number else add to temp_max. Continue until you see all the numbers. A separate bookkeeping variable for positions is required. The time is O(n).

It can also be done using a Dynamic Programming approach, where the core recursive solution consists of storing the value of maximum sum seen so far for each number. Everytime you see another number, the decision involves either taking the number to increase the previous sum or not. However this approach requires O(n^2).

It can be done in O(n) by converting the numbers into nodes, the edges become the weight of the number. Add a dummy source which links to all the nodes via a weighted edge where the weight is the number is itself. (s->1 has an edge weight 1). Add a dummy destination, which links to all the nodes except the source via an edge weight of 0. Now the problem reduces to finding the Longest Path in the Directed Acyclic Graph.

In the kadane's algorithm, can anyone tell me how to print the start and end of that maximum subarray.

ankit gupta's code but a bit modified and made simpler to understand, and yes in python:

def max_subarray(A):
    max_so_far = max_ending_here = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
        print  max_ending_here, max_so_far
    return max_so_far

if __name__ == "__main__":
    B = [2, -3, 10, -8, 9, -4, 1, -7]
    print max_subarray(B)

what about {-1,-3,-2,-1,-4}

the code will give 0.

Code given by Ankit Gupta is incorrect. It will give correct value of sum as the code has been taken from Programming Pearls. However,it gives wrong values of from and to.
Ex {8,10,-10,-7,1,25}
Output:
Maxsum: 27  from = 4 & to = 5.. 
It should have been from = 0 and to = 5

This can be another solution to same problem

typedef struct index_details
{
int start;
int end;
int sum;
} index_details_t;

index_details_t * __mmaxsub(int start,int end,int arr[],index_details_t *__mindexinfo)
{
int i;
int sum=0,max_sum = arr[start];;

for(i=start;i<=end;i++)
{
sum += arr[i];
if(max_sum < sum)
{
__mindexinfo->start = start;
__mindexinfo->end=i;
__mindexinfo->sum = sum;
max_sum = sum;
}
}
return __mindexinfo;
}

#define MAX_ARRAY_SIZE 9

int main()
{
index_details_t indexinfo[2] = {{0,0,0},{0,0,0}};
int numarr[MAX_ARRAY_SIZE] = {-2,1,-3,4,-1,2,1,-5,4};
int i;
int sum = 0, max_sum = numarr[0];


for(i=0;i<=MAX_ARRAY_SIZE-1;i++)
{
__mmaxsub(i,MAX_ARRAY_SIZE-1,numarr,&indexinfo[1]);

if(max_sum < indexinfo[1].sum)
{
indexinfo[0].start = indexinfo[1].start;
indexinfo[0].end=indexinfo[1].end;
indexinfo[0].sum = indexinfo[1].sum;
max_sum = indexinfo[1].sum;
}
}


printf("\n Max Subarray \n");

for(i=indexinfo[0].start;i<=indexinfo[0].end;i++)
printf("\t %d",numarr[i]);

printf("\n Done \n");
return 0;
}

easy one , get Cumlative sum , put zero where it is -ve , in second step start finding MAX ,

Best way is to load the entire array into a graph & assign each element of the array as the weight of an edge. So, the graph will have n edges & n+1 vertices (where n is the number of elements in the array). Now, find the longest path in this graph. It is not easy to find the longest path in a graph (unlike shortest path). We need to design some efficient algorithm.

What if all the numbers are negative?

Hi, I am new to this interview type question.

This problem is solvable with Interval tree in O(NlogN). I don't think any O(N) solution exists for this.

#include <stdlib.h>
#include <iostream>
using namespace std;

int main()
{
//Array containing the integers
int array[]= {-2, 1,-3, 4,-1,2,1,-5,4,2,-17,9,-2,4, 5, -4};
int total = 0;
int start = 0;
int finish = 0;
int highest = 0;
int tempstart = 0;
for(int i=0;i <=sizeof(array)/sizeof(int) - 1; i++)
{
total = total + array[i];
total = total < 0 ? 0: total;
if(total <= 0)
tempstart = i+1;
highest = highest < total ? total:highest;
if(total >= highest)
{
start = tempstart;
finish = i;
}
}
cout<<"from "<<start<<" to "<<finish<<" Produce:- "<<highest<<endl;
return 0;
}

cant get better than this one... this is the best... i tried it

public final class MaxSumTest
{
static private int seqStart = 0;
static private int seqEnd = -1;

public static int maxSubSum3( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;

for( int i = 0, j = 0; j < a.length; j++ )
{
thisSum += a[ j ];

if( thisSum > maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
else if( thisSum < 0 )
{
i = j + 1;
thisSum = 0;
}
}

return maxSum;
}
public static void main( String [ ] args )
{
int a[ ] = { 4, -3, 5, -2, -1, 2, 6, -2 };
int maxSum;


maxSum = maxSubSum3( a );
System.out.println( "Max sum is " + maxSum + "; it goes"
+ " from " + seqStart + " to " + seqEnd );

}
}

Finds the Sub-Array of any size with Maximum sum.

INPUT

A===>Array In which SubArray To Find

n===>Size of Array

pk===>Pointer to k which give lower index of sub-array

pl===>Pointer to l which give upper index of sub-array

Returns the sum of sub-array

int LargestSum(int * A,int n,int* pk,int* pl)
{
*pk = *pl = 0;
int sum = 0;
int maxsum = 1<<31;
for(int i = 0; i < n; ++i){
sum += A[i];
if(maxsum < sum){
maxsum = sum;
*pl = i;
}
else if(sum < 0){
sum = 0;
}
}

int j = *pl;
int temp = maxsum;
while(temp)
{
temp = temp - A[j];
j--;
}

*pk = j + 1;
return maxsum;
}

For what it matters, here my O(n) linear programming solution

#include<iostream>

using namespace std;

void findMaxSub(int *a, int count) {
	if (count == 1 || count == 0) {
		cout << "Trivial case";
	}

	int sum[count];
	sum[0] = a[0];
	int start = 0;
	int startmax = 0;
	int endmax = 0;
	int max = a[0];

	for (int i = 1; i < count; i++) {
		if (sum[i - 1] <= 0) {
			//Largest sum of previous elements is zero or negative
			sum[i] = a[i];
			start = i;
		} else {
			sum[i] = a[i] + sum[i - 1];
		}

		//Check if new max
		if (sum[i] > max) {
			max = sum[i];
			endmax = i;
			startmax = start;
		}
	}

	cout << startmax << " " << endmax << " " << max << endl;
}

int main() {
	int a[] = { -111, -9, -8, 7, -2, -3, 4, 5, 7, -6 };

	findMaxSub(a, sizeof(a) / sizeof(int));
}

Kadane's_Algorithm:

#include<iostream>
#include <stdlib.h>
using namespace std;

int max_of(int first, int second)
{
   return first > second ? first : second;
}

      int main()

      {
          int a[] = {1, -2, -3, 4, 5, 7, -6};
          int max_so_far = 0;
          int max_now_here = 0;
          for(int i=0; i<6;i++)
          {
            max_now_here = max(0, max_now_here + a[i]);
            max_so_far = max(max_so_far , max_now_here);
          }

          cout<< "The max sum is : "<< max_so_far;

        return 0;

      }

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

main()
{


int array[10]= { -111, -9, -8, 7, -2, -3, 4, 5, 7, -6};


int max = -99999;
int curSum = 0;

int a=0 , b =0, s=0, i = 0;

for( i = 0; i < 10; i++ )
{
curSum += array[i];

if ( curSum > max )
{
max = curSum;
a = s;
b = i;
}

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

else
{
s = i;
}
}
}


printf("Sum-> %d s=%d f=%d\n",max,a,b);
return 0;
}

public static int[] maxSubsequence(int[] A) {
int start = 0, end = 0;
int startPrev = 0, endPrev = 0;
int sum = 0;
int preSum = 0;
boolean restart = false;
for (int i = 0; i < A.length; i++) {
if (restart) {
restart = false;
start = i;
sum = 0;
}

if (A[i] >= 0) {
sum += A[i];
end = i;
if (i == A.length - 1) {
if (sum > preSum) {
preSum = sum;
startPrev = start;
endPrev = end;
}
}
} else {
restart = true;
if (sum > preSum) {
preSum = sum;
startPrev = start;
endPrev = end;
}
}
}
int[] ret = new int[]{startPrev, endPrev};
return null;
}

int MaxSum(const vector<int>& v, int& start, int& end)
{
   int max = v[0];
   int sum = v[0];
   int j;
   start = 0;
   end = 0;
   for (int i = 1; i < v.size(); ++i)
   {
      if (sum > 0) {
         sum += v[i];
      } else {
         sum = v[i];
         j = i;
      }
      if (sum > max) {
        max = sum;
        end = i;
        start = j;
      }
   }
   return max;
}

public class Subarray {

private int startIndex;
private int endIndex;
private int maxSum = 0;

public void getSubArraySum(int[] a)
{
int thisSum = 0;
for(int i=0, j=0; j<a.length; j++)
{
thisSum = thisSum + a[j];
if(thisSum > maxSum)
{
maxSum = thisSum;
startIndex = i;
endIndex = j;
}
else
{
maxSum = 0;
i=j+1;
}
}
}

public static void main(String args[])
{
Subarray subArr = new Subarray();
int[] a = {1, -2, 5, -2, 4, 5, 2};
subArr.getSubArraySum(a);
System.out.println(subArr.startIndex);
System.out.println(subArr.endIndex);
System.out.println(subArr.maxSum);
}
}

public static int findMaxSubArray(int[] array)
{
int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0;
while(i<array.length)
{
if(cumulativeSum+array[i]<0)
{
cumulativeSum=0;
start=i+1;
}
else
cumulativeSum=cumulativeSum+array[i];
if(cumulativeSum>max)
{
max=cumulativeSum;
savepoint=start;
end=i;
}
i++;
}

System.out.println("Max : "+max+" Start indices : "+savepoint+" end indices : "+end);
return max;

}

Here's my JavaScript O(n) implementation

function find_maximum_subsequence(seq) {
	var result, lower_idx, upper_idx, max_sum, working_sum, i;

	max_sum = 0;

	for (i = 0; i < seq.length; i++) {
		if (seq[i] > 0) {
			lower_idx = i;
			working_sum = seq[i];
			i++;

			while (i < seq.length && seq[i] > 0) {
				working_sum += seq[i];
				i++;
			}

			if (working_sum > max_sum) {
				max_sum = working_sum;
				upper_idx = i - 1;
			}
		}
	}

	if (lower_idx && upper_idx) {
		result = {
			lower_idx: lower_idx,
			upper_idx: upper_idx,
			sum: max_sum
		}
	} else {
		result = false;
	}

	return result;
}

console.log(find_maximum_subsequence([1, -2, -3, 4, 5, 7, -6]));

Assuming input is an integer array 'a' and there is atleast 1 +ve number. This is O(n) algorithm

int max=0, start=0, end=0, sum=0
for(int i=0; i<a.length; i++){
	sum=sum+a[i];
	if(sum < 0 )
        {
		sum=0;
		start=i+1;
		end=i+1;
	}
	else if (sum>max){
		max=sum;
		end=i;
	}
}

There is a simple solution.

int maxSum (int [] a) {
  int sum = 0;
  int max = 0;
  for (int i = 0; i < a.length(); i++) {
    sum += a[i];
    if (max < sum) {
      max = sum;
    } else if (sum < 0) {
      sum = 0;
    }
   return max;
}

int array[] -> given array;
int maxval, startindex,endindex;
for(int i = 0;i<n;i++)
{ 
if(a[i] > 0)
{  for(int j=i+1;j<n;j++)
   { if(a[j] > 0)
      { max[i] += a[j] ;
      }
      else break;
   }
} 
}

sort max[] according to increasing order and we have solution in the last element ... vola!!!

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

int max_sub_seq_sum(int* arr, int n, int &start, int &end)
{
	int curr_sum = 0, max_sum = 0;
	int curr_start = 0;

	for (int i = 0; i < n; i++)
	{
		if (curr_start == -1)
			curr_start = i;

		curr_sum += arr[i];

		if (curr_sum < 0)
		{
			curr_sum = 0;
			curr_start = -1;
		}
		if (curr_sum > max_sum)
		{
			max_sum = curr_sum;
			start = curr_start;
			end = i;
		}
	}

	return max_sum;

}

What if the input is {5,15,-30,1,-5,40,10}. It will print 50 instead of 55 {1, -5, 40, 10}. help please?

public void findLargestSum(int[] B){
int[] B = {1, -2, -3, 4, 5, 7, -6};
int startIndex = 0;
int endIndex = 0;
int maxTotal = 0;
int tempTotal = 0;

for(int i=0;i<B.length;i++){
for(int j=i;j<B.length;j++){
tempTotal = tempTotal + B[j];
if(tempTotal>maxTotal){
maxTotal=tempTotal;
endIndex = j;
startIndex = i;
}
}
tempTotal = 0;
}
System.out.println("MaxTotal is : "+maxTotal);
System.out.println("Start Index is : "+startIndex);
System.out.println("End Index is : "+endIndex);

}

What if all the numbers are negative?