Kadane's algorithm

Abstract

---

• Kadane’ algorithm: given an Array of elements $A$, the maximum sum of contiguous subarray at index $i$, $localMax(i)$ is the maximum of element at index $i$, $A[i]$ and the sum of element at index $i$ and the maximum sum of contiguous subarray at index $i-1$, $A[i]+localMax(i-1)$
• From the Recurrence Function $localMax(i)$, we can see that if the maximum sum of contiguous subarray at index $i-1$ is negative, the maximum sum of contiguous subarray at index $i$, $localMax(i)$ is definitely the element at index $i$, in another word, we are actually starting a new subarray

Attention

Maximum sum of contiguous subarray at index $i$ must include the element at index $i$.

Maximum Subarray Problem

---

• Maximum Subarray Problem is the task of finding the largest possible sum of a contiguous subarray, within a given one-dimensional Array of numbers
• This problem can be solved efficiently in $O(n)$ using Kadane’s algorithm which computes the largest possible sum of a contiguous subarray at each index. The answer is just the biggest number among all the largest possible sum of contiguous subarray at each index

Attention

The contiguous subarray is an non-empty subarray. If the given array only has negative numbers, the maximum subarray should be an empty subarray which has a sum of $0$. But the solution with Kadane’s algorithm will return the smallest value from the array.

We can definitely modify the solution a bit to adapt to this edge case. For example, we can have a variable that returns true if all the elements in the array are negative, then we just return $0$ when the variable is true.

Top-down DP Approach

$$localMax(i)=\{\begin{array}{ll}0& i=0\\ A[1]& i=1\\ max(A[i],A[i]+F(i-1))& i\ge 2\end{array}$$

• This Top-down DP Approach doesn’t require DP Table as the Optimal Substructure (最优子结构) removes the Overlapping Subproblems (重复子问题). The State Transition Equation (状态转移方程) shown above is the core of this top-down DP approach
• The globalMax variable is used to keep track of the biggest number among all the largest possible sum of contiguous subarray at each index

class Solution {
  int globalMax;
  public int maxSubArray(int[] nums) {
	if (nums.length == 0) return 0;
	if (nums.length == 1) return nums[0];
	
    globalMax = nums[0];
    localMax(nums, nums.length - 1);
    return globalMax;
  }
 
  public int localMax(int[] nums, int currIndex) {
    if (currIndex == 0)
      return nums[0];
 
    int localMax =
        Math.max(nums[currIndex], localMax(nums, currIndex - 1) + nums[currIndex]);
    globalMax = Math.max(globalMax, localMax);
    return localMax;
  }
}

Bottom-up DP Approach

• In Bottom-up DP Approach, we can see the maximum subarray with the inclusion of element at current index is the maximum of the element at the current index and the sum of element at current index + maximum subarray at the previous index
• The globalMax variable is used to keep track of the biggest number among all the largest possible sum of contiguous subarray at each index

class Solution {
  public int maxSubArray(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
 
    int globalMax = nums[0];
    int localMax = nums[0];
    for (int i = 1; i < nums.length; i++) {
      localMax = Math.max(nums[i], localMax + nums[i]);
      globalMax = Math.max(globalMax, localMax);
    }
    return globalMax;
  }
}

Maximum Product Subarray

---

• Maximum Product Subarray is the task of finding the largest possible product of a contiguous subarray, within a given one-dimensional Array of numbers

Key point

It is a more advanced version of Maximum Subarray Problem, because the largest possible product can consist of negative numbers since negative $\times$ negatives produces positive. However, negative $\times$ positive produces negative.

If we use Kadane’s algorithm to find the maximum product of a contiguous subarray at index $i$, there is NO WAY to find the largest product if it consists of two negative numbers, for example. This is because, once we encounter a negative number, we discard it since a positive number multiplied by a negative number is negative, unless the two negative numbers are the first elements. The solution is to keep track of the minimum product of a contiguous subarray at index $i$ as well, and the maximum product of a contiguous subarray at index $i$ depends on it!

Top-down DP Approach

$$minVal(i)=\{\begin{array}{ll}0& i=0\\ A[1]& i=1\\ min(A[i],A[i]\ast minVal(i-1),A[i]\ast maxVal(i-1))& n\ge 2\end{array}$$ $$maxVal(i)=\{\begin{array}{ll}0& i=0\\ A[1]& i=1\\ max(A[i],A[i]\ast maxVal(i-1),A[i]\ast minVal(i-1))& n\ge 2\end{array}$$

• This Top-down DP Approach requires maxArr and minArr to function as DP Table to avoid duplicated computation
• The State Transition Equation (状态转移方程) shown above is the core of this top-down DP approach. The globalMax variable is used to keep track of the biggest number among all the largest possible product of contiguous subarray at each index

class Solution {
  int globalMax;
  int[] maxArr;
  int[] minArr;
  public int maxProduct(int[] nums) {
    if (nums.length == 0)
      return 0;
    if (nums.length == 1)
      return nums[0];
 
    maxArr = new int[nums.length];
    minArr = new int[nums.length];
 
    Arrays.fill(maxArr, Integer.MIN_VALUE);
    Arrays.fill(minArr, Integer.MAX_VALUE);
 
    globalMax = nums[0];
    maxVal(nums, nums.length - 1);
    return globalMax;
  }
 
  public int minVal(int[] nums, int currIndex) {
    if (currIndex == 0)
      return nums[0];
    if (minArr[currIndex] != Integer.MAX_VALUE)
      return minArr[currIndex];
 
    int currVal = nums[currIndex];
 
    int localMin = Math.min(currVal,
        Math.min(currVal * minVal(nums, currIndex - 1),
            currVal * maxVal(nums, currIndex - 1)));
 
    minArr[currIndex] = localMin;
    return localMin;
  }
 
  public int maxVal(int[] nums, int currIndex) {
    if (currIndex == 0)
      return nums[0];
    if (maxArr[currIndex] != Integer.MIN_VALUE)
      return maxArr[currIndex];
 
    int currVal = nums[currIndex];
    int localMax = Math.max(currVal,
        Math.max(currVal * minVal(nums, currIndex - 1),
            currVal * maxVal(nums, currIndex - 1)));
 
    globalMax = Math.max(globalMax, localMax);
    maxArr[currIndex] = localMax;
    return localMax;
  }
}

Bottom-up DP Approach

• In Bottom-up DP Approach, we can see the maximum subarray with the inclusion of element at current index is the maximum of the element at the current index, minimum product at the previous index $\times$ element at current index, maximum product at the previous index $\times$ element at current index
• The globalMax variable is used to keep track of the biggest number among all the largest possible product of contiguous subarray at each index

class Solution {
  public int maxProduct(int[] nums) {
    if (nums.length == 0)
      return 0;
    if (nums.length == 1)
      return nums[0];
 
    int maxVal = nums[0];
    int minVal = nums[0];
    int globalMax = nums[0];
 
    for (int i = 1; i < nums.length; i++) {
      int currVal = nums[i];
 
      int localMax =
          Math.max(currVal, Math.max(minVal * currVal, maxVal * currVal));
      int localMin =
          Math.min(currVal, Math.min(maxVal * currVal, minVal * currVal));
 
      globalMax = Math.max(globalMax, localMax);
      maxVal = localMax;
      minVal = localMin;
    }
 
    return globalMax;
  }
}

Best Time to Buy and Sell Stock

---

• Best Time to Buy and Sell Stock is the task of finding the largest possible profit of a given one-dimensional Array of numbers, the profit is the difference between the number at the right side and the number on the left side

Key point

This can be solved with Kadane’s algorithm, we calculate the minimum cost of purchasing the stock at each index, which is used to calculate the profit on the next index. Each index here denotes a specific day.

Top-down DP Approach

$$minCost(i)=\{\begin{array}{ll}A[1]& i=1\\ min(A[i],minCost(i-1))& n\ge 2\end{array}$$

• This Top-down DP Approach requires minArr to function as DP Table to avoid duplicated computation
• The State Transition Equation (状态转移方程) shown above is the core of this top-down DP approach. The maxProfit variable is used to keep track of the biggest profit among all the best deals we can make on each day

class Solution {
  int[] minArr;
  public int maxProfit(int[] prices) {
    if (prices.length <= 1)
      return 0;
 
    int maxProfit = 0;
    minArr = new int[prices.length];
    Arrays.fill(minArr, Integer.MAX_VALUE);
 
    for (int i = 1; i < prices.length; i++) {
      int currPrice = prices[i];
 
      maxProfit = Math.max(maxProfit, prices[i] - minCost(prices, i - 1));
    }
    return maxProfit;
  }
 
  public int minCost(int[] prices, int currIndex) {
    if (currIndex == 0)
      return prices[0];
    if (minArr[currIndex] != Integer.MAX_VALUE)
      return minArr[currIndex];
 
    int currCost = prices[currIndex];
    int currLowestCost = Math.min(currCost, minCost(prices, currIndex - 1));
    minArr[currIndex] = currLowestCost;
    return currLowestCost;
  }
}

Bottom-up DP Approach

• In Bottom-up DP Approach, we use minCost to hold the smallest cost of purchase a stock til that particular index, which is used to calculate the best deal on the next index
• The maxProfit variable is used to keep track of the biggest profit among all the best deals we can make on each day

class Solution {
  public int maxProfit(int[] prices) {
    if (prices.length <= 1)
      return 0;
 
    int minCost = prices[0];
    int maxProfit = 0;
 
    for (int i = 1; i < prices.length; i++) {
      int currPrice = prices[i];
 
      maxProfit = Math.max(maxProfit, currPrice - minCost);
      minCost = Math.min(minCost, currPrice);
    }
 
    return maxProfit;
  }
}

References

---

• Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work? | by Rohit Singhal | Medium