Kadane's Algorithm

Kadane's Algorithm is the best algorithm to find the subarray which has the maximum sum among all the subarrays.

arr[]={-5, 4,  6, -3 , 4, -1}

In tis array, the subarray as {4, 6, -3 , 4 } has maximum sum.

The Simplest Approach to solve this problem is to find the sum of all subarrays and then print the subarray with the max sum. But as it will take two iterations therefore the time complexity comes in order of n² . 

By using Kadane's Algorithm the time complexity reduces drastically.

Aproach

As soon as the element of the subarray is positive in those cases we can add it to the sum. 

Therefore, if the cumulative sum of any subarray is coming to be negative, then avoid that part. 

Start from the beginning and add the elements, and store the maximum of the cumulative sum, if the sum becomes negative then delete that part and start again from the next index.

1. Create two variables as maxSum and cumSum and equate both to 0.

2. Run a loop from 0 to n times.

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
  
}

3. Calculate the cumulative sum of the Subarray as

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
}

4. If the cumSum is greater than that of maxSum then store it in that.

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
   
   if(cumSum>maxSum){
      maxSum=cumSum;
   }
}

5. As we discussed if the cumulative sum becomes negative then avoid that. As the maximum sum that it can produce is already stored in the variable maxSum. Therefore if  cumSum becomes negative then revalue it as 0 and start again from next index as

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
   
   if(cumSum>maxSum){
      maxSum=cumSum;
   }
   
   if(cumSum<0){
      cumSum=0;
   }
}

6. After iterating through the whole array the maximum sum is stored in the variable maxSum.

Keep in mind that if the maximum sum of the subarray is negative then we have to modify the function accordingly, Try it once by yourself

Time Complexity Analysis

As we only iterate through the array once as a result the time complexity is O(n). Which is a great improvement over the previous approach.

To know more about Kadane's Algorithm

Kadane's Algorithm