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!
Related posts:
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?