minimum sum subarray in O(N) by Kadane's algorithm

15
votes

We all know about the maximum sum subarray and the famous Kadane's algorithm. But can we use the same algorithm to find minimum sum also?

My take is:

change the sign and find the max sum in that, same as the way we calculate the maximum sum subarray. Than change the sign of the elements in the array to make it in initial state.

Please help me in correcting the algo if it has any issue.

corner case: I know there is an issue if all the elements are positive and we can handle this case by doing some preprocessing i.e. traverse the array if all are +ve than just return the minimum number from the array.

The above mention algorithm will work and well supported (explained) by dasblinkenlight.

3
javaarraysalgorithm
Why does it not work if all elements are positive? Minimum sum in that case is 0 for the empty sequence and that will be correctly found. – Henry
@Henry - He probably wants to find the minimum sum of a size-k subarray for some k ≤ N. – DaoWen
in that case we can traverse the array and if we see that all elements are +ve than we can take the minimum of the elements, which is more appropriate than retuning 0. Thanks. but the main question here is, will the approach that i have mentioned will work to find the minimum sum or not? – Trying

3 Answers

8
votes

Will the approach that I have mentioned work to find the minimum sum?

Yes, it will. You can re-state the problem of finding the minimum sum as finding a negative sum with the largest absolute value. When you switch the signs of your numbers and keep the rest of the algorithm in place, that's the number that the algorithm is going to return back to you.

I know there is an issue if all the elements are positive

No, there's no issue: consider the original Kadane's algorithm when all elements are negative. In this case the algorithm returns an empty sequence for the sum of zero - the highest one possible under the circumstances. In other words, when all elements are negative, your best solution is to take none of them.

Your modified algorithm is going to do the same in case when all numbers are positive: again, your best solution is to not take numbers at all.

If you add a requirement that the range returned back from the algorithm may not be empty, you could modify the algorithm slightly to find the smallest positive number (or the greatest negative number) in case when Kadane's algorithm returns an empty range as the optimal solution.

1
votes

Just replace max with min.

//O(n)
public static int minSubArraySum(int[] arr) {
    int minSum = 0;
    int curSum = 0;
    for (int num : arr) {
        curSum += num;
        minSum = Math.min(minSum, curSum);
        curSum = Math.min(curSum, 0);
    }
    return minSum;
}
0
votes
static void subArraySumMin(int a[]) {
        int minendingHere = 0;
        int minSoFar = a[0];

        for (int i = 1; i < a.length; i++) {
            minendingHere = Math.min(a[i], minendingHere + a[i]);
            minSoFar = Math.min(minSoFar, minendingHere);
        }

        System.out.println(minSoFar);
    }