Whether you want to uncover the secrets of the universe, or you just want to pursue a career in the 21st century, basic computer programming is an essential skill to learn.
Kadane's Algorithm
Welcome back, dear reader. So, how is it going?
In this article, we will discuss a very interesting and new algorithm called KADANE'S ALGORITHM
So, what is this algorithm used for? Let's find out.
We are given an input array. We have to find the maximum subarray sum i.e.
the largest sum that a subarray has in the input array. Remember that a subarray is continuous.
Subset and Subarrays are two completely different things. For instance:
In the image above, the largest subarray sum is 23 of the subarray marked with yellow. We don't have to find the subarray, we just have to tell the maximum subarray sum.
We recommend you refer to the KADANE'S ALGORITHM VIDEO to understand the problem.
Also, we suggest that you try to think of an O(n) time solution for this problem.
If you can come up with that, it will probably be Kadane's Algorithm only.
Approach
Time Complexity: O(n) where n is the number of elements in the array
Space Complexity: O(1)
Explanation:
Consider the same input array as shown above (img-1).
We will maintain two lists (not in the program,
just for explanation purposes).
One is the current best subarray sum and the other will be the overall best subarray
sum as shown in the diagram below (img-2).
So, the current best now has 4-4 written under it which indicates that the current best sum is 4
and the list has only one element i.e. 4.
The overall best subarray till now is also 4 and its sum is 4.
We have also kept a variable "i" at 1. So, let's start the traversal.
The value arr[i]=3. If we do not include this value in the subarray then a new subarray
will be formed with only 3 as the element. So, the sum of that subarray will be 3. If we include this element 3 in the previous subarray only, we get the subarray as {4,3} and the sum will be 7. This is greater than the previous sum and also the overall best till now.
So, we will select 3 to be a part of the previous subarray only
Now, we are at arr[2]. The value here is negative.
So, if we do not include it in the previous subarray, the sum will be -2 only and the only element will be -2. If we include it, the total sum will become 7 + (-2)=5.
So, we will include it in the previous subarray only.
This is because a new subarray can start at every element or the element may
get included in the previous subarray only. We want to have the maximum sum subarray in
the overall best result. Hence, we try to maximize the subarray sum at every element index,
and then if it is greater than the already present overall best sum,
we change the overall best sum value.
Now, let us try to solve the next element. What do you think we should do?
Try yourself and match with the answer shown below:
So, we have changed the overall best and the current best both. Why? Think!!
Now we are at arr[4]. The value here is -14. If we do not include this value in the previous subarray, a new subarray will be formed and the sum will be -14. If we include it, the sum will be 11 + (-14)=-3.
So, the sum will be greater in this way.
So, we will include -14 and the current best sum will be -3
whereas the overall best sum will be kept untouched.
Now we are at arr[5]. Here, we have the value 7. So, if we add 7 to the previous subarray,
the sum will be -3 + 7=4 whereas, it alone has a sum of 7.
So, we will not add this into the previous subarray and a new
subarray will start from here.
So, we have come to some conclusions till here:
If the previous subarray sum is positive, it does not matter whether
the next element is negative or positive,
add it to the previous subarray sum to get the current best sum.
If the previous subarray sum is negative, it does not matter whether the current element is negative or positive, we will not add it to the previous subarray; rather, we will start a new subarray and the current best sum will be the element itself.
At every index, check if the current best sum is greater than the overall best sum or not. If it is, update the overall best sum too.
So, this will be the procedure that we have to follow. We recommend you refer to the following solution video to understand the procedure completely.
We also suggest that before going to the solution video, continue with the above process with the above-mentioned rules to get the maximum subarray sum.
This will give you a great insight into the problem.
Now that we have understood everything, let's write the code for the same.
import java.io.*;
import java.util.*;
public class Main {
//Kadane's Algorithm
public static int solution(int[] arr) {
int csum=arr[0];
int maxSum=arr[0];
for(int i=1;i < arr.length;i++)
{
if(csum < 0)
{
csum=arr[i];
}
else
{
csum=csum+arr[i];
}
if(maxSum < csum)
{
maxSum=csum;
}
}
return maxSum;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = scn.nextInt();
}
System.out.println(solution(arr));
}
}
java;
true";
The above code is explained in the following solution video.
You may refer to it if you have any doubts regarding the code.
Let us now discuss the time and space complexity of Kadane's Algorithm.
Time and Space Complexity Analysis
Time Complexity:
The time complexity of the above code is O(n). This is because we are just traversing
a 1-D array only once i.e.
we are visiting all the elements in the input array only once.
Space Complexity:
The space complexity for the above code is O(1) as we have not used any extra memory.
So, dear reader, we hope that you have understood this problem completely and the above explained
Kadane's Algorithm and its code too. If you have any doubts regarding anything, we suggest you refer to the complete solution video to clear all your doubts. With this,
we have completed this solution.
Suggestions
Here are some suggestions from our side that you do not want to miss:
We recommend you refer to the solution video once. This will help you understand the complete procedure slowly and in-depth.
We also suggest that you try to code the brute force approach of this problem too as you should be able to write the brute force approach in the interviews first and then optimize it. So, keep practicing and working hard. Till then, Happy Coding!!!
