Random integers in an array. Find the largest sum of a continuous subset

Question

I had an interview question that I never had. Apparently, there is a "very efficient" algorithm to solve it.

Question: Given a given array of random positive and negative numbers, find the continuous subset that has the largest sum.

Example:

[1, -7, 4, 5, -1, 5]

The best subset is {4, 5, -1, 5}

I can come up with no solution other than brute force. What is an effective method?

Answer 1

Go to the list, tracking the local amount of list items so far. If the local amount is the highest, then keep it.
If the local amount reaches 0 or lower, then reset and restart it from the next item.

Theory

If the current sum of the subset is greater than zero, it will contribute to future sums of the subset, so we will keep it. On the other hand, if the current sum of a subset is zero or lower, it will not contribute to future sums of the subset. Therefore, we discard it and start with the new sum of the subset. Then it's just a matter of tracking when the current amount of the subset is greater than any previous meeting.

pseudo code

In-parameter - an array of list length N The result is stored in best_start and best_end .

 best_sum = -MAX best_start = best_end = -1 local_start = local_sum = 0 for i from 0 to N-1 { local_sum = local_sum + list[i] if local_sum > best_sum { best_sum = local_sum best_start = local_start best_end = i } if local_sum <= 0 { local_sum = 0 local_start = i+1 } } 

Answer 2

Convert the list to a list of total amounts, [1,-7,4,5,-1,5] to [1, -6, -2, -3, 2] . Then go through the list of total amounts, still maintaining the smallest value and the maximum difference between what you see as the current value and what is currently the smallest value. Got it from here

Answer 3

You can answer this CLRS question, which includes a hint:

Use the following ideas to develop a non-recursive linear time algorithm for the problem with maximum subarability.

Start at the left end of the array and move towards the right, tracking the maximum subarak seen so far.

Knowing the maximum auxiliary array A[1..j] , continue the answer to find the maximum subarax ending in index j+1 using the following observation:

the maximum auxiliary array A[1..j+1] is either the maximum auxiliary array A[1..j] or the auxiliary array A[i..j+1] for some 1 <= i <= j + 1 .

Determine the maximum auxiliary array of form A[i..j+1] in constant time, based on the knowledge of the maximum subaram ending in index j .

 max-sum = A[1] current-sum = A[1] left = right = 1 current-left = current-right = 1 for j = 2 to n if A[j] > current-sum + A[j] current-sum = A[j] current-left = current-right = j else current-sum += A[j] current-right = j if current-sum > max-sum max-sum = current-sum left = current-left right = current-right return (max-sum, left, right) 

Answer 4

Too bad that Java does not have a return tuple type. Thus, it was necessary to print the indices and summarize in the method.

 public class Kadane { public static void main(String[] args) { int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3}; findMaxSubArray(intArr); } public static void findMaxSubArray(int[] inputArray){ int maxStartIndex=0; int maxEndIndex=0; int maxSum = Integer.MIN_VALUE; int sum= 0; for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) { int eachArrayItem = inputArray[currentIndex]; sum+=eachArrayItem; if( eachArrayItem > sum){ maxStartIndex = currentIndex; sum = eachArrayItem; } if(sum>maxSum){ maxSum = sum; maxEndIndex = currentIndex; } } System.out.println("Max sum : "+maxSum); System.out.println("Max start index : "+maxStartIndex); System.out.println("Max end index : "+maxEndIndex); } } 

And here's some shameless marketing: I managed to put together a slide about how it works

Answer 5

Here is a java class that works in linear time

 public class MaxSumOfContinousSubset { public static void main(String[] args) { System.out.println(maxSum(1, -7, 4, 5, -1, 5)); } private static int maxSum (int... nums) { int maxsofar = 0; int maxhere = 0; for (int i = 0; i < nums.length; i++) { maxhere = Math.max(maxhere + nums[i], 0); maxsofar = Math.max(maxhere, maxsofar); } return maxsofar; } }