Kadane’s Algorithm Explained with Examples

Too Long; Didn't Read

Given an array, the algorithm to find the maximum subarray sum is called Kadane’s Algorithm. It can be applied to a 1D array or 2D matrix. The algorithm can be of any dimension. We could optimize the space complexity by taking dp[i-1] which is the previous sum into a variable, eliminating the need for dp[] array. We have two choices: either start at the current index or add the current element to the maximum of 0 and previous sum.