Kadane’s Algorithm

You might have come across Kadane’s algorithm and thought that it might be difficult so you may have skipped it. But hold on, cause the universe has given you this golden opportunity to learn this algorithm one more time, naah I am just kidding.

Stick through this bulletin to understand this algorithm in and out. I am sure that you would understand this algorithm once you go through this diligently.

If you have been solving questions on arrays then you might have stumbled across the problem of finding the “Maximum sub-array problem” wherein you need to find the sub-array which has the maximum sum.

This problem can be solved using multiple approaches like ,

1. Finding sum of all possible sub-arrays and then finding the maximum sum. This is a brute force approach and hence is neither time or space efficient as time complexity is O(n³) and space complexity is O(n).
2. This can be even solved using recursion but since the input can be very very large hence the call stack might overflow.
3. But the most efficient way to solve this is using Kadane’s algorithm which has time complexity O(n) and space complexity O(1).

Kadane’s algorithm has a dynamic programming aspect to it.

What exactly is dynamic programming ?

It is a method for solving a complex problem by breaking down into simpler sub problems, and solving each of those sub problems just once, and storing their solutions in the memory-based data structure (like arrays, maps, vector, etc) so the next time the same sub-problem occurs, instead of recomputing its solution, one can simply look up for it in the previously computed solutions and hence saving the computation time that is time required is reduced.

In the Kadane’s algorithm we are going to follow the same pattern that is breaking down the problem into sub problems and then storing the solutions in the memory based data structure.

Before diving into the algorithm part we should know what exactly is a sub-array ?

A sub-array is nothing but a contiguous part of an array.

Suppose we have an array, arr = [1,2,3,4,5]

then the sub-arrays can be, [1], [3,4], [1,2,3,4,5], [2,3] ; but [1,4] is not a sub-array as the elements in the sub-array should be contiguous part of the array.

Algorithm:

It is a fairly simple algorithm to understand and perform as well.

You will understand it in a better way once you go through this example.

In case of the above example, the maximum sum would be 6.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int sum = 0;
    int maxsum = INT_MIN;
    vector<int> v = {1,2,-34,8,9};
    for(auto value : v)
    {
        sum += value;
        maxsum = max(maxsum, sum);
        if(sum<0)
        {
            sum = 0;
        }
    }
    cout << maxsum << endl;
    return 0;
}

public class kadane 
{
    public static void main(String[] args) {
        int arr[] = {1,2,-34,8,9};

        int sum = 0;
        int maxsum = Integer.MIN_VALUE;
        for(int i=0;i<arr.length;++i)
        {
            sum+=arr[i];
            if(sum>maxsum) maxsum = sum;
            if(sum<0) sum = 0;
        }

        System.out.println("Maximum sum : " + maxsum);
    }
}

Time and Space complexity :

Time complexity: O(n)

Space complexity: O(1)

Maximum Subarray - LeetCode

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.