Kadane's Algorithm

Problem Link

53. Maximum Subarray – LeetCode

Problem Statement

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

Examples

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum = 23.

Constraints

• 1 <= nums.length <= 10⁵

• -10⁴ <= nums[i] <= 10⁴

Intuition

This is a classic problem of dynamic programming. The key idea is:

• At each index, decide whether to extend the previous subarray or start a new subarray from current element.

• We want to maximize the subarray sum globally.

This is best solved using Kadane’s Algorithm in O(n) time.

Approach: Kadane’s Algorithm

1. Initialize:

   • maxSum = nums[0]

   • currSum = nums[0]

2. Loop through i = 1 to n - 1:

   • currSum = max(nums[i], currSum + nums[i])
     (either extend the subarray or start new from current)

   • maxSum = max(maxSum, currSum)

3. Return maxSum

Java Code

class Solution {
    public int maxSubArray(int[] nums) {
        int currSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
        }

        return maxSum;
    }
}

Time and Space Complexity

Dry Run

Input:

nums = [-2,1,-3,4,-1,2,1,-5,4]

Steps:

• i=0 → currSum = -2 → maxSum = -2

• i=1 → currSum = max(1, -2+1) = 1 → maxSum = 1

• i=2 → currSum = max(-3, 1-3) = -2 → maxSum = 1

• i=3 → currSum = max(4, -2+4) = 4 → maxSum = 4

• i=4 → currSum = max(-1, 4-1) = 3 → maxSum = 4

• i=5 → currSum = max(2, 3+2) = 5 → maxSum = 5

• i=6 → currSum = max(1, 5+1) = 6 → maxSum = 6

• i=7 → currSum = max(-5, 6-5) = 1 → maxSum = 6

• i=8 → currSum = max(4, 1+4) = 5 → maxSum = 6

→ Return 6

Follow-up: Divide and Conquer Approach (Advanced)

• Divide array into two halves.

• Recursively compute:

  • Max subarray sum in the left half

  • Max subarray sum in the right half

  • Max subarray sum that crosses the mid

• Return the max of the three.

Time: O(n log n)

Kadane’s Algorithm is preferred due to O(n) time.

Conclusion

The Maximum Subarray problem is a foundational problem for understanding prefix sums, dynamic programming, and divide-and-conquer strategies.

Kadane’s Algorithm provides an elegant and efficient solution by:

• Carrying forward only beneficial subarrays.

• Avoiding unnecessary recomputation.

It’s widely applicable in many financial, data stream, and performance optimization scenarios.