# 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.

`nums[] = {-1, 2, 3, -4, 5}              ^         ^            start      endoutput : 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-1`th 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_MINfor 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.

## More from Ayush Verma

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