I just learned about this algorithm, which is considered a dynamic programming approach. However, depending on the implementation, it might not resemble dynamic programming at all.

Check out the implementation presented on Wikipedia:

def max_subarray(numbers): """Find the largest sum of any contiguous subarray.""" best_sum = 0 current_sum = 0 for x in numbers: current_sum = max(0, current_sum + x) best_sum = max(best_sum, current_sum) return best_sum

That does not look like dynamic programming to me. Now let’s look at the following implementation:

// Kadane's algorithm // f(i) stores the max sub array sum ending at i // Base case: f(0) = A[0] // f(i) = max(f(i - 1) + A[i], A[i]); int maxSubArray(vector<int>& A) { int n = static_cast<int>(A.size()); vector<int> dp(n + 1); dp[0] = A[0]; int max = dp[0]; for (int i = 1; i < n; i++) { dp[i] = std::max(dp[i-1] + A[i], A[i]); max = std::max(max, dp[i]); } return max; }

Can you see it now? I’m sure you do.

Of course, the second implementation uses additional space, the purpose is to show the recurrence function (thus DP).

## Practice

Try solving the following problem using Kadane’s algorithm: https://leetcode.com/problems/maximum-subarray.