Kadanes Algo [V.V.V.V.V IMP]

Problem Statement

Given an integer array, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

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

Intuition

Check all possible subarrays and calculate their sums. Keep track of the maximum sum found.

Algorithm

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

public class Solution {
    public int maxSubArrayBruteForce(int[] nums) {
        int n = nums.length;
        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 using constant extra space

Approach 2: Kadane's Algorithm (Optimal)

Intuition

The key insight is that at each position, we have two choices:

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

We choose the option that gives a larger sum. If the previous sum becomes negative, it's better to start fresh.

Algorithm

1. Initialize maxSum and currentSum with the first element
2. For each element from index 1:
   • currentSum = max(nums[i], currentSum + nums[i])
   • maxSum = max(maxSum, currentSum)
3. Return maxSum

public class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            // Either extend previous subarray or start new one
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
    
    // Alternative implementation (more intuitive)
    public int maxSubArrayAlt(int[] nums) {
        int maxSum = nums[0];
        int currentSum = 0;
        
        for (int num : nums) {
            currentSum += num;
            maxSum = Math.max(maxSum, currentSum);
            // Reset if sum becomes negative
            if (currentSum < 0) {
                currentSum = 0;
            }
        }
        
        return maxSum;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only using constant extra space

Follow-up: Print the Subarray

Key Takeaways

1. Kadane's Algorithm is a classic example of dynamic programming
2. The core idea: decide at each step whether to extend or restart
3. A negative running sum should be discarded (start fresh)
4. This algorithm is fundamental for many subarray problems
5. Can be extended to find the actual subarray indices
6. Works even when all elements are negative