How to Find the Minimum Sum Subarray in O(N) Using Kadane's Algorithm?

How can I determine the minimum sum subarray in linear time using Kadane's algorithm?

// Example implementation of Kadane's algorithm for minimum sum subarray
int minSubArray(int[] nums) {
    int minCurrent = nums[0];
    int minGlobal = nums[0];

    for (int i = 1; i < nums.length; i++) {
        minCurrent = Math.min(nums[i], minCurrent + nums[i]);
        if (minCurrent < minGlobal) {
            minGlobal = minCurrent;
        }
    }
    return minGlobal;
}

Kadane's algorithm is typically used to find the maximum sum subarray, but with a slight modification, it can also effectively find the minimum sum subarray in O(N) time complexity. The algorithm works by iterating through the array while maintaining the current minimum subarray sum found so far and the overall global minimum.

public class MinSumSubarray {
    public static void main(String[] args) {
        int[] nums = {2, -1, -2, 1, -4, 3};
        System.out.println("Minimum Sum Subarray: " + minSubArray(nums));
    }

    public static int minSubArray(int[] nums) {
        int minCurrent = nums[0];
        int minGlobal = nums[0];

        for (int i = 1; i < nums.length; i++) {
            minCurrent = Math.min(nums[i], minCurrent + nums[i]);
            if (minCurrent < minGlobal) {
                minGlobal = minCurrent;
            }
        }
        return minGlobal;
    }
} // This code snippet demonstrates the implementation of finding the minimum sum subarray.

Causes

• The algorithm efficiently handles both positive and negative integers.
• It allows for the quick identification of the minimum contiguous subarray.

Solutions

• Initialize two variables: minCurrent (to track the current minimum) and minGlobal (to track the overall minimum) with the first element of the array.
• Iterate through the array starting from the second element, updating minCurrent as the minimum of the current element and minCurrent plus the current element.
• Update minGlobal whenever minCurrent is less than minGlobal.

Mistake: Not initializing minGlobal properly.

Solution: Always initialize minGlobal with the first element of the array to handle possible edge cases.

Mistake: Incorrectly updating minCurrent.

Solution: Ensure that the minCurrent is calculated by considering both the current element and the sum with the previous minimum.