Largest Sum Contiguous Subarray or KADANE’S ALGORITHM
In this question we have to find the maximum sum of the subarray of the original array. Now one would ask what is a subarray and how it is different from subsequence. a subarray is a contiguous or consecutive part of the original array which means it occupies consecutive position of original array while subsequence might not take continues position of the original array.
Suppose the array is like this {-2, 1, -3, 4, -1, 2, 1, -5, 4} in this their are many subarrays possible like {-2,1,-3),{4,-1,2,1,-5},{2,1,-5,4} with their sums as -4, 1, 2 respectively and many more subarrays are also possible but the subarray {4,-1,2,1} will produce the max sum of 6.
If we use Brute force approach here, we first select the one element and then select all other elements and form subarray from it and calculate sum of each subarray it will take quadratic time O(n²) which is not optimal at all. so to optimise the solution in linear time O(n) we here use Kadane’s algorithm.
In kadane’s algorithm the main idea is to maintain a set of all positive contagious part at each index of the array (Currsum is used here) and maintain maximum sum contiguous segment among all positive segments (maxsum used here) . Here we compare maxsum with currsum, if currsum comes greater than maxsum we update the value of maxsum as currsum and if currsum comes negative we assign it with value 0 (as we don’t want to get negative contagious sum)
Code for the kadane’s algorithm is as follows:-
#include <iostream>
using namespace std;int kadane(int arr[], int n){int maxsum = 0;
int currsum = 0;for (int i = 0; i < n; i++){currsum = currsum + arr[i];if(currsum>maxsum){
maxsum=currsum;
}if(currsum<0){
currsum=0;
}}
return maxsum;}
int main(){int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int n = sizeof(arr)/sizeof(arr[0]);cout << "The maximum sum of a contiguous subarray is " <<
kadane(arr, n);return 0;}
Complexities is as follows
Time complexity :- Big O(n)(Array is traversed only once here)
Space complexity:- Big O(1) ( No Auxiliary space is used here)
[ n = size of the input ]
Some important properties of Kadane’s algorithm are:-
1) If our Array contains all the Positive elements or non-negative elements then our maximum subarray sum is the Sum of entire array itself as all the elements would be included.
2) if our Array contains all the Negative elements or non-positive elements then our maximum subarray sum would be the subarray of size 1 having the max value out of all other elements.
3) Different subarray can have the same maximum subarray sum
Some Applications of kadane’s algorithm are in Business Firm , in which company has to find the duration in which they experienced the maximum growth. Its also used in Computer vision area in which we have to find the brightest area in Bitmap images and also in genome analysis to find the correct segment of protein sequences and many more..
