KADANE’S ALGORITHM

A Brief Introduction

Problem Statement – Find the maximum sum sub-array of the given array

Let us assume the maximum sum sub-array lies between index L to R. We can actually look at it as prefix sum [1,R] – prefix sum [1,L-1]. To maximize this difference, we need to maximize the ps[1,R] and minimize the ps[1,L-1].

Another trivial but important condition while performing above algo is L <= R. So, let us assume that we are scanning the array and at each ith position, we assume the ps[1,R] is nothing but ps[1,i], it means assume ith position as the best position to get the maximum subarray sum.

We, now need to subtract the minimum possible ps[1, L] from it. Let us say, the variable min_sum stores the minimum possible sum seen so far.

The variable best will store the best possible answer for us. The variable curr_sum calculates the prefix sum for us.

The leetcode problem is exactly this, you can try your hands on the algorithm here – https://leetcode.com/problems/maximum-subarray/

class Solution {
public:
    int maxSubArray(vector<int> nums) {
        
        int best = INT_MIN;
        int min_sum= 0;
        int curr_sum = 0;
        for(int i=0;i<nums.size();i++){
            curr_sum += nums[i];
            best = max(best,curr_sum - min_sum);
            min_sum = min(min_sum, curr_sum);
        }
        return best;
    }
};

We will see more variations of this algorithm in later sections. Some problems we will be dealing in this section are :

  1. https://www.codechef.com/DEC18A/problems/CBFEAST
  2. https://www.codechef.com/ACMKOL15/problems/KOL15B
  3. https://acm.timus.ru/problem.aspx?space=1&num=1146
  4. https://codeforces.com/contest/1359/problem/D
  5. https://codeforces.com/contest/817/problem/D
  6. https://codeforces.com/problemset/problem/327/A

Leave a Reply