Find Largest sum contiguous Subarray [V. IMP]

Problem Statement

Given an array of integers (can contain both positive and negative numbers), find the contiguous subarray with the largest sum and return that sum. This is the famous Kadane's Algorithm problem.

Example:

• Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
• Output: 6
• Explanation: The subarray [4, -1, 2, 1] has the largest sum = 6

Approach 1: Brute Force (Check All Subarrays)

Intuition

Generate all possible subarrays and calculate their sums. Track the maximum sum found.

Algorithm

1. Use two nested loops to generate all subarrays
2. For each subarray, calculate its sum
3. Track the maximum sum

public class Solution {
    public int maxSubArraySum(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        
        int maxSum = Integer.MIN_VALUE;
        
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Two nested loops
• Space Complexity: O(1) - Only variables used

Approach 2: Kadane's Algorithm (Optimal)

Intuition

At each position, we have two choices:

1. Extend the previous subarray by including current element
2. Start a new subarray from current element

We choose whichever gives us a larger sum. The key insight is: if the sum up to the previous element is negative, it's better to start fresh.

Algorithm

1. Initialize currentMax = nums[0] and globalMax = nums[0]
2. For each element from index 1:
   • currentMax = max(nums[i], currentMax + nums[i])
   • globalMax = max(globalMax, currentMax)
3. Return globalMax

public class Solution {
    public int maxSubArraySum(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        
        int currentMax = nums[0];
        int globalMax = nums[0];
        
        for (int i = 1; i < n; i++) {
            // Either extend previous subarray or start new
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            globalMax = Math.max(globalMax, currentMax);
        }
        
        return globalMax;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only two variables

Variant: Return the Subarray Itself

public class Solution {
    public int[] maxSubArrayWithIndices(int[] nums) {
        int n = nums.length;
        if (n == 0) return new int[]{0};
        
        int currentMax = nums[0];
        int globalMax = nums[0];
        int start = 0, end = 0, tempStart = 0;
        
        for (int i = 1; i < n; i++) {
            if (nums[i] > currentMax + nums[i]) {
                currentMax = nums[i];
                tempStart = i;
            } else {
                currentMax = currentMax + nums[i];
            }
            
            if (currentMax > globalMax) {
                globalMax = currentMax;
                start = tempStart;
                end = i;
            }
        }
        
        // Return sum and indices
        return new int[]{globalMax, start, end};
    }
}

Variant: Handle All Negative Numbers

The standard Kadane's algorithm handles this correctly. If all numbers are negative, it returns the largest (least negative) number.

Key Takeaways

1. Kadane's Algorithm is a classic example of dynamic programming
2. The key insight: negative prefix sum is useless - start fresh
3. Time complexity is optimal at O(n) with O(1) space
4. The algorithm naturally handles arrays with all negative numbers
5. This technique extends to other problems like maximum product subarray
6. Understanding the "extend or restart" decision is crucial
7. Related problems: Maximum Circular Subarray Sum, Maximum Subarray with at most K swaps