Magic of Kadane Algorithm ?

Let Understand step By Step

Let's understand step By step:

What is the Kadane algorithm ?

Kadane's Algorithm, renowned for its simplicity and efficiency, elegantly solves the problem of finding the maximum subarray sum in a given array. Its brilliance lies in its straightforward approach, making it a staple in the toolbox of any programmer dealing with arrays.

Let Understand What's the need of this algorithm ?

Understand it by a simple Questions:

Given an integer array nums, find the subarray with the largest sum, and return its sum.?

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cout << "Enter the size of the array: ";
    cin >> N;

    int arr[N];
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    int max_sum = INT_MIN;

    // Iterate over all subarrays
    for (int i = 0; i < N; i++) {
        int current_sum = 0;
        for (int j = i; j < N; j++) {
            // Calculate the sum of the current subarray
            current_sum += arr[j];
            // Update max_sum if current_sum is greater
            if (current_sum > max_sum) {
                max_sum = current_sum;
            }
        }
    }

    cout << "The sum of the contiguous subarray with the largest sum is: " << max_sum << endl;

    return 0;
}
        

We can see that we can solve it by using for loop and it takes a time Complexity of O(n^2) and this is not optimal, so how can we make it optimal, for that we have a kadane Algorithm.

What is the approach to it ?

Kadane's Algorithm is an efficient way to solve the maximum subarray problem. It avoids the need for nested loops and achieves a linear time complexity.

Pseducode:

Initialize: ? ?

max_so_far = INT_MIN ?

max_ending_here = 0

Loop for each element of the array

? (a) max_ending_here = max_ending_here + a[i] ?

(b) if(max_so_far < max_ending_here) ? ? ? ? ?

? max_so_far = max_ending_here ?

(c) if(max_ending_here < 0) ? ? ? ? ?

? max_ending_here = 0

return max_so_far

Code for it:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        int max_so_far=nums[0];
        int currentSum=nums[0];
        for(int i=1;i<nums.size();i++){
        
            if(currentSum<0){
                currentSum=0;
       }
       currentSum=currentSum+nums[i];
       
        if(currentSum>max_so_far)
        {
            max_so_far=currentSum;
        }
    }
        return max_so_far;
        
    }
};        

This approach has a time complexity of O(N), where N is the size of the array.

The main difference between Kadane's Algorithm and the "normal" algorithm lies in their approach and efficiency in solving the maximum subarray problem.

1. Nested Loop (Normal) Algorithm:The normal algorithm uses nested loops to iterate over all possible subarrays. It calculates the sum of each subarray and keeps track of the maximum sum found so far. This approach has a time complexity of O(N^2), where N is the size of the array, due to the nested loops.
2. Kadane's Algorithm:Kadane's Algorithm scans the array only once, which makes it more efficient. It keeps track of two variables: max_ending_here and max_so_far.max_ending_here represents the maximum sum of a subarray ending at the current position.max_so_far represents the maximum sum of any subarray seen so far. At each element, it decides whether to extend the current subarray or start a new subarray.This approach has a time complexity of O(N), where N is the size of the array.

In summary, Kadane's Algorithm is more efficient than the normal nested loop approach because it reduces the time complexity from O(N^2) to O(N), making it the preferred choice for solving the maximum subarray problem in terms of time complexity.

#KadanesAlgorithm #MaximumSubarray #EfficientAlgorithm