Course contentsShow
← Computer Science
Lesson 939 of 2,87222. Dynamic ProgrammingFree lesson

Maximum Subarray Sum (Kadane's as DP)

Find contiguous subarray with maximum sum using dynamic programming state transition approach.

Maximum Subarray Sum (Kadane's as DP)

You'll learn how to find the contiguous subarray with the largest sum using dynamic programming state transitions.

The Core Idea

Imagine you're walking through an array of numbers (positive and negative), and at each position you must decide: "Should I extend my current subarray to include this element, or abandon what I had and start fresh from here?"

This is a classic DP problem with optimal substructure and overlapping subproblems. The key insight: at each position i, the maximum sum ending exactly at that position depends only on the maximum sum ending at position i-1.

State Definition and Transition

State: Let dp[i] = maximum subarray sum ending at index i.

Transition: At each position, you have two choices:

  1. Extend the previous subarray: dp[i-1] + arr[i]
  2. Start a new subarray: arr[i]

Choose whichever is larger: dp[i] = max(arr[i], dp[i-1] + arr[i])

Base case: dp[0] = arr[0] (first element has no choice)

The final answer is the maximum value in the entire dp array, since the best subarray could end anywhere.

Example

Array: [-2, 1, -3, 4, -1, 2, 1]

  • dp[0] = -2
  • dp[1] = max(1, -2+1) = 1 (start fresh)
  • dp[2] = max(-3, 1-3) = -2 (extend reluctantly)
  • dp[3] = max(4, -2+4) = 4 (start fresh)
  • dp[4] = max(-1, 4-1) = 3 (extend)
  • Continue...

This transforms the classic Kadane's greedy algorithm into an explicit DP formulation, showing how it fits the memoization/tabulation pattern.

Key Takeaway: Maximum subarray sum is a DP problem where each state tracks the best sum ending at that position, transitioning by choosing to extend or restart the subarray.