Kadane's algorithm

Hello everyone! in this post, we'll discuss kadane's algorithm. I'll try to keep it as simple as possible. The goal of this algorithm is to find a maximum value of the sub-array sum. Let's take an example to understand.

arr = [7,2,-1,-3,9]

the maximum sub array sum is = 7+2-1-3+9 = 14

How do we find this? well, the naive approach is to get all sub-array sums and find the maximum.

Let's say we have an array [a1, a2, a3, a4]

We'll start with a1 and find all the different sub-arrays

Now, we get maximum of all i.e. max(a1+a2, a1+a2+a3, a1+a2+a3+a4, a2+a3, a2+a3+a3, a3+a4)

Well, this works but let's analyze the time complexity. The pseudo-code looks like this

result = -infinity
for i 0...n
    for j in i+1...n
       result = max(result, a[i] + a[j])
return result

This will give O(n^2) time complexity.

Let's see how we can optimize this

From the above image, we see that there are repeated computations i.e. overlapping sub-problems. If we find the maximum of a1+a2 and a1+a2+a3 gives a solution for a sub-problem. We can prove the fact by induction that when combining solutions of all sub-problems will give the overall solution i.e. optimal sub-structure.

From these two facts, we can say that we're using a dynamic programming approach.

The idea is to find the maximum of all nested sub-problems eventually we'll reach the solution.

As depicted in the above image it is very clear that max(a1+a2, a1+a2+a3) gives a local maximum when we do this for all sub-problems we'll get the global maximum.

at every j, local_max holds maximum sum A[i] + A[i+1] + .... A[j-1] for all i ∈ {1....j}. So, local_max + A[j] contains next local maximum. By the end we reach n it'll contain maximum of {1....n-1} elements which gives our result

Let's write code

def find_max_sub_array_sum(arr):
  local_max = arr[0]
  global_max = float('-inf')
  for i in range(1,n):
    local_max = max(arr[i], arr[i] + local_max)
    global_max = max(local_max, global_max)
  return global_max

After learning kadane's algorithm, let's try to solve this problem https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

From the problem description, we need to maximize the profit by finding optimal buy and sell prices. You cannot sell first and buy later.

Example : [7, 1, 5, 3, 6, 4]

Answer: we'll buy on day 2 at price 1 and sell on day 5 at price 6 with a total profit of $5.

When I first saw this problem and the above example, I thought of a solution to find the index of minimum elements. From that index, traverse the whole array and find the maximum which will give our answer. But, I was wrong. Let's see how

From the above chart, we can see that the minimum value is -1. After -1, the maximum value is 6. The total profit we get is 7. But, there's another case prior to a minimum which is 2 and 11 which gives a profit of 9. This proves that the above approach is wrong.

We need to apply kadane's algorithm, but with a slight change. Here, we need to find the maximum sub-array sum of stock price differences. Let's see how this works.

let A be the list of stock prices where A[i] represents stock price on the day i.

let's assume A = [a1, a2, a3, a4]

our aim is to maximize profit which means maximize the difference, let B = [a1, a2-a1, a3-a2, a4-a3]

let's say a2 and a4 give the maximum profit, so in B we need to find the sum of (a3-a2) + (a4-a3) = a4-a2. Hence, we need to find the largest sub-array sum of price differences

def max_profit(prices):
    local_max = 0
    global_max = 0
    for i in range(1, len(prices)):
        local_max += (prices[i] - prices[i-1])
        local_max = max(0, local_max)
        global_max = max(local_max, global_max)
    return global_max

Code Explanation

We can do this in two ways. First, find another array with difference of prices and find a maximum subarray. For that, we need two iterations and another array. (or) find the difference of prices in the same iteration (refer to line no. 5 in the above code). The rest of the code is self-explanatory.