Kadane’s Algorithm

Maximum subarray problem

Problem:
In a given set of Numbers in a One-Dimensional array, Our Task is to find the largest Sum of a Subarray.

For example, for the array of values [−2, 1, −3, 4, 2, 1, −5, 4], the contiguous subarray with the largest sum is [4, 2, 1], with — 7.

Before Jumping to Solution Let us see How we can approach the given problem.

Photo by Mohammad Rahmani on Unsplash

Brute Force:

The brute approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible or not.

• Run the first loop from 0 to n — 1, where n is the size of the array. — Counter i
• Next, we will run a nested loop from i to n — 1 and add the value of the element in the nested loop to a variable currentMax.
• Lastly, for every subarray, we will check if the currentMax is the maximum sum of all contiguous subarrays.

The problem with this approach is that it will take
Time complexity: O(N²), Where N is the size of the array.
Space complexity: O(1)

Efficient Approach :

Kadane’s original algorithm solves the problem version when empty subarrays are admitted. It scans the given array from left to right. In the jth step, it computes the subarray with the largest sum ending at each element, this sum is maintained in the variable current_sum. Moreover, it computes the subarray with the largest sum anywhere in the array by maintaining in a variable, and easily obtained as the maximum of all values current_sum seen so far.

The idea is basically memoizing the value of current_sum for each element and checking the largest among them.

Lets take the example:
    {-2, -3, 4, -1, -2, 1, 5, -3}

    max_so_far = max_ending_here = 0

    for i=0,  a[0] =  -2
    max_ending_here = max_ending_here + (-2)
    Set max_ending_here = 0 because max_ending_here < 0

    for i=1,  a[1] =  -3
    max_ending_here = max_ending_here + (-3)
    Set max_ending_here = 0 because max_ending_here < 0

    for i=2,  a[2] =  4
    max_ending_here = max_ending_here + (4)
    max_ending_here = 4
    max_so_far is updated to 4 because max_ending_here greater 
    than max_so_far which was 0 till now

    for i=3,  a[3] =  -1
    max_ending_here = max_ending_here + (-1)
    max_ending_here = 3

    for i=4,  a[4] =  -2
    max_ending_here = max_ending_here + (-2)
    max_ending_here = 1

    for i=5,  a[5] =  1
    max_ending_here = max_ending_here + (1)
    max_ending_here = 2

    for i=6,  a[6] =  5
    max_ending_here = max_ending_here + (5)
    max_ending_here = 7
    max_so_far is updated to 7 because max_ending_here is 
    greater than max_so_far

    for i=7,  a[7] =  -3
    max_ending_here = max_ending_here + (-3)
    max_ending_here = 4

Pseudo Code:

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 :

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

If you have any suggestions please feel free to connect with us or comment with your thoughts.

Happy Coding.