Question: You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum.
Answer: This is an all-time favorite software interview question. The best way to solve this puzzle is to use Kadane’s algorithm which runs in O(n) time. The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values. Here’s some code to illustrate.
void maxSumSubArray( int *array, int len, int *start, int *end, int *maxSum )
{
int maxSumSoFar = -2147483648;
int curSum = 0;
int a = b = s = i = 0;
for( i = 0; i < len; i++ ) {
curSum += array[i];
if ( curSum > maxSumSoFar ) {
maxSumSoFar = curSum;
a = s;
b = i;
}
if( curSum < 0 ) {
curSum = 0;
s = i + 1;
}
}
*start = a;
*end = b;
*maxSum = maxSumSoFar;
}
Think you have a better solution? We'd love to read your comments!
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
//Updated solution
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]max)
{
max=cumulativeSum;
savepoint=start;
end=i;
}
i++;
}
//There was some mistake in my previous //solution. Find Updated One
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]max)
{
max=cumulativeSum;
savepoint=start;
end=i;
}
i++;
}
System.out.println(“Max : “+max+” Start indices : “+savepoint+” end indices : “+end);
return max;
}
//Time complexity O(n)
//space complexity : Zero
public static void main(String… args)
{
int[] array={1,2,3,4,-9,6,7,-8,1,9};
System.out.println(findMaxSubArray(array));
}
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]max)
{
max=cumulativeSum;
savepoint=start;
end=i;
}
i++;
}
System.out.println(“Max : “+max+” Start indices : “+savepoint+” end indices : “+end);
return max;
}
This algorithm fails with the following values
int arr[]={2,4,-5,6,8,12,-5,3,-4,49,45,-11,2,99};
here largest sub array is {2,99}
but the output shows only {99}
public class Test {
static int A[]={8,-8,9,-9,10,-11,12};
public static int maxConsecutiveSum(int A[], int N){
int start = 0;
int end = N;
int sum = 0;
int maxSum = 0;
int maxSumIndex = 0;
int i=start;
while(i != end) {
sum = sum + A[i];
if(sum > maxSum ) {
maxSum = sum;
maxSumIndex = start;
}
if (sum < 0) {
end = start -1;
if (end < 0) end = end + N - 1;
start = i+1;
i = start;
sum = 0;
continue;
}
i++; if (i == N) i=0;
}
System.out.println("max sum is =" + maxSum + "start element is" + maxSumIndex);
return maxSum;
}
/**
* @param args
*/
public static void main(String[] args) {
maxConsecutiveSum(A,7);
}
}
Why not just iterate through the entire array, add only its positive members to the sub-array and maintain a cum of the members added.
Also, I don’t understand the curSum < 0 check. This check always gets thrown if the entire input array contains negative values. Even if curSum decreases in value, that doesn't mean it isn't beneficial to maintain the start index. the array {1000, -1, 1000} is a simple counterexample
I dont understand why you pass arguments start and end and return void. Redefining start and end within the method doesn’t change them outside the method’s environment since they’re both integers. Also, MaxSum is never initialized in the code
Here is my answer:
Step1: Sort the array in ascending order.
Step2: Calculate the sum of all positive numbers and calculate the sum of all negative numbers.
Step3: Compare the values of these 2 (-ve and +ve) to decide the largest…
Here’s some code that works for these tests
bool findMaxSubArray(const int *arr, const int arraySize, int *start, int *end, int *sum) {
if(arraySize <= 0)
return false;
// Intitialize
*start = 0;
*end = 0;
*sum = arr[0];
int tempSum = *sum;
int tempStart = *start;
int tempEnd = *end;
bool startNewRange = false;
bool addToCurrentRange = false;
for(int i = 1; i < arraySize; i++) {
// case 1: adding current element increases tempSum
// case 1a: tempSum = 0
// addToCurrentRange = true;
// case 2: adding current element decreases tempSum
// startNewRange = true;
// case 3: adding current element keeps tempSum unchanged
// case 3a: tempSum = 0
// addToCurrentRange = true;
// case 1
if(tempSum + arr[i] > tempSum) {
if(tempSum < 0) { // case 1a
startNewRange = true;
} else { // case 1b
addToCurrentRange = true;
}
}
// case 2
if(tempSum + arr[i] < tempSum) {
startNewRange = true;
}
// case 3
if(tempSum + arr[i] == tempSum) {
if(tempSum = *sum) {
// we found a higher sum
// save it
*sum = tempSum;
*start = tempStart;
*end = tempEnd;
}
}
return true;
}
Has a bug. Here are some results
4, -2, 7, 4, -8, -6, 2, 9, 1, 0, -4
start: 0 end: 3 sum: 13
FAILED
-4, -2, -7, -4, -8, -6, -2, -9, -1, -3, -4
start: 8 end: 8 sum: -1
PASSED
-4, -2, -7, -4, -8, 0, -2, -9, -1, -3, -4
start: 5 end: 5 sum: 0
PASSED
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
start: 0 end: 10 sum: 66
PASSED
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
start: 0 end: 0 sum: 0
PASSED
Taking care of special case when all the numbers are negative..
int arrayMax = Integer.MIN_VALUE;
int arrayMaxIndex = -1;
for(int i = 0; i arrayMax)
{
arrayMax = arr[i];
arrayMaxIndex = i;
}
}
for(int i = 0; i maxSum)
{
e = i;
maxSum = curSum;
}
if (curSum < arrayMax) {
// curSum has reduced, so start again
curSum = 0;
s = i + 1;
}
}
if (maxSum == arrayMax)
{
// s changes always in this case, make it equal to e
s = e;
}
#include
int main()
{
int a[10]={2,5,-4,9,4,-14,-9,7,12,-13};
int i,sum1=0,s2=0,max=0;
for(i=0;i0)
sum1=sum1+a[i];
else
{
s2=sum1;
sum1=0;
}
if(s2>sum1) max=s2;
else max=sum1;
}
printf(“%d”,max);
return ;
}
I think the original solution fails for this series 1,2,3,4,5,-1,7,8,9,10
Did someone verify this ?
scan the elements one by one untill u encounter a negative value…once u get a -ve value add all the previous elements store it in some location…perform this by neglecting th negative values repeatedly…..then sort the sum values…represent the biggest sum …
I have written a small function to get the max sum of the sub array in a given array . Please let me know if it fails at any case.
public static void maxSumSubArray(int[] arr){
int maxSum=arr[0];
int sumTillPos=arr[0];
for (int i = 1; i maxSum){
maxSum=sumTillPos;
}
if(arr[i]>maxSum){
maxSum=arr[i];
sumTillPos=arr[i];
}
}
System.out.println(“max sum sub array ::”+maxSum);
}
what about doing a Merge sort (nlogn) or any other sort that is O(nlogn), and then test if the max value is =< 0 we just take that first element, if not we will be iterating until we get the first element that is =< 0 and we do not include it in the sub array.
Yes Deepak, that would be O(n^2) which is not very ideal. The solution given is only O(n).
Loop over the main array and create a new array which stores the sum of numbers in array
Eg.
sum_array[1] = array[1] + array[2]
sum_array[2] = array[1] + array[2]+array[2]
and so on..
Once we the sum_array find out the maximum of sum_array.
And repeat the same from array[2] to last
May be this algorithm takes O(n^2).
public static Integer[] subArrayWithLargestSum(Integer[] array) {
List intList = new ArrayList();
if (array.length > 0) {
// first check to see if we get all positive number sub-array
for (Integer i: array) {
if (i > 0) intList.add(i);
}
// check to see if it has any ZERO number
if (intList.size() == 0) {
for (Integer i: array) {
if (i == 0) {
intList.add(0);
break;
}
}
}
// means all are negative values
if (intList.size() == 0) {
Integer max = array[0];
for (Integer i: array) {
if (i >= max) {
intList.remove(max);
intList.add(i);
max = i;
}
}
}
}
return intList.toArray(new Integer[0]);
}
Good site 🙂
would this code work?
n = a.length;
maxSum[n – 1] = a[n – 1]; //stores max possible sum starting from position i
endPos[n – 1] = n – 1; //stores the length of max possible sum starting from i, ending at endPos[i] (inclusive)
for(int i = n – 2; i >= 0; i–)
{
int x = a[i] + maxSum[i + 1];
if(x >= a)
{
maxSum[i] = x;
endPos[i] = end[i + 1];
}
else
{
maxSum[i] = a[i];
endPos[i] = i;
}
}
Yes we are looking for a contiguous sub-array in this case. If not, instead of sorting, you could just add all the positive integers in the array.
Actually sorting wont work if you have to have a contigious sub-array.
Could you sort the array and then work from the tail end backwards until you hit < 0?