Kadane’s Algorithm

Kadane’s Algorithm or maximum subarray sum helps us to find the maximum sum of consecutive values in an array.

Now, for an example let’s take an array [-1,2,4,-3,5,2,-5,2], we assume that an empty subarray is allowed, so maximum subarray sum is always atleast 0. There’s various approaches to solve this question.

Algo 1

In this approach, we go through all the possible subarrays, calculate the sum of values in each subarray and maintain the maximum sum.

best = 0
n = len(nums)
for i in range(0,n):
   for j in range(i,n):
      sum = 0
      for k in range(i,j+1):
          sum+=nums[k]
          best = max(best,sum)
print(best)

The time complexity of this approach is O(n³) as it contains three nested loops

Algo 2

There’s another way we can improve this code by using two nested loops and having a time-complexity of O(n²). This is possible by calculating the sum at the same time when the right end of the subarray moves.

best = 0
n = len(nums)
if n==1:
   return nums[0]
for i in range(0,n):
   curr_sum = 0
   for j in range(i,n):
       curr_sum += nums[j]
       best = max(curr_sum,best)
print(best)

Algo 3

Surprisingly, it is possible to solve the problem in O(n) time3 , which means that just one loop is enough. The idea is to calculate, for each array position, the maximum sum of a subarray that ends at that position. After this, the answer for the problem is the maximum of those sums. Consider the subproblem of finding the maximum-sum subarray that ends at position k. There are two possibilities: 1. The subarray only contains the element at position k. 2. The subarray consists of a subarray that ends at position k −1, followed by the element at position k. In the latter case, since we want to find a subarray with maximum sum, the subarray that ends at position k −1 should also have the maximum sum. Thus, we can solve the problem efficiently by calculating the maximum subarray sum for each ending position from left to right

best = 0
sum = 0
n = len(array)
for k in range(0,n):
  sum = max(array[k],sum+array[k])
  best = max(sum,best)
print(best)

The algorithm only contains one loop that goes through the input, so the time complexity is O(n). This is also the best possible time complexity, because any algorithm for the problem has to examine all array elements at least once.