An Intuitive Approach to Understanding Kadane’s Algorithm.

My rant about what’s wrong with how it’s taught and an unorthodox introduction to Dynamic Programming.

Photo by Blake Connally on Unsplash
nums[] = {-1, 2, 3, -4, 5}
^ ^
start end
output : 6
int sum = 0, globalmax = 0;
for i in {0... nums.size() - 1}:
sum = 0;
for j in {i... nums.size() - 1}:
sum += nums[j];
globalsum = max(sum, globalsum);
return globalsum;
nums[] = {-1, 2, 3, -4, 5}
  • Or we can start a new subarray here with just the element at n-1th index in it.
nums[] = {-1, 2, 3, -4, 5} // let's assume n = 3
^
int GetMaxSub(int nums[], int n):
// base case
return max(nums[n - 1], nums[n - 1] + GetMaxSub(nums, n - 1))
int GetMaxSub(int nums[], int n):
if(n == 1) return a[n - 1] //base case
return max(nums[n - 1], nums[n - 1] + GetMaxSub(nums, n - 1)
int gmax = INT32_MIN
for i in range(1, nums.size()):
gmax = max(gmax, GetMaxSub(nums, i)
return gmax

Engineer-in-making by the day, hobbyist writer by the night. A bit of both during weekends.