Tag Kadane's Algorithm

Maximum Sum SubArray Problem

Arunima Mandal Leave a comment

Approach 1: Kadane’s Algorithm

Though it’s a particular algorithm, if one is good at programming, this approach is more intuitive than any other approach without knowing that this is actually an algorithm! 

#include<bits/stdc++.h>

using namespace std;

int maxSumSubArray(int a[], int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0, start =0, end = 0, s=0;
    //cout<<"max_so_far "<<max_so_far<<endl;

    for (int i=0; i< size; i++ )
    {
        max_ending_here += a[i];

        if (max_ending_here > max_so_far)
        {
            max_so_far = max_ending_here;
            start = s;
            end = i;
        }

        if (max_ending_here < 0)   ///If that is any negative number, we discard it
        {
            max_ending_here = 0;
            s = i+1; ///and start considering from the next index.That is we are rightfully assuming
                    ///that the beginning & ending of the subsequence can't contain any negative number.
        }
    }
    cout << "Maximum contiguous sum is "
        << max_so_far << endl;
    cout << "Starting index "<< start
        << endl << "Ending index "<< end << endl;
}

/*Driver program to test maxSumSubArray*/
int main()
{
    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(a)/sizeof(a[0]);
    int max_sum = maxSumSubArray(a, n);
    return 0;
}

If the problem states that the subarray would have to be of k size, fear not! That solution is not much different from the above approach. We have just to modify the above solution a bit in that case.

#include<bits/stdc++.h>

using namespace std;

int maxSumSubArray(int a[], int size, int k)
{
    if(k>size) cout<<"Invalid"<<endl;

    int sum=0,maxi=-100000,start=0,endi;
    for(int i=0;i<k;i++) sum+=a[i];
    maxi=sum;
    for (int i=k; i< size; i++ )
    {
        sum+= a[i]-a[i-k];
        if(sum>maxi)
        {
            maxi=sum;
            start= i-k+1;
            endi=i;
        }
    }
    cout<<"Maximum sum "<<maxi<<endl;
    cout<<"Start at index "<<start<<" and ends at index "<<endi<<endl;
    return maxi;

}

/*Driver program to test maxSumSubArray*/
int main()
{
    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int k=3;
    int n = sizeof(a)/sizeof(a[0]);
    int max_sum = maxSumSubArray(a, n, k);
    return 0;
}

Approach 2: Using DP(Dynamic Programming)

This method is also intuitive for solving the problem if one is comfortable using the DP algorithm.

#include <bits/stdc++.h>

using namespace std;

int maxSumSubArray_dp(int nums[], int size)
{
    int dp[100005]= {0};
    dp[0] = nums[0];
    int maxi = dp[0];
    for (int i = 1; i < size; i++)
    {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        maxi = max(maxi, dp[i]); // find max in dp
    }
    return maxi;
}

int main()
{
    int nums[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(nums)/sizeof(nums[0]);
    int max_sum = maxSumSubArray_dp(nums, n);
    cout<<"Maximum Sum Subarray using DP is "<<max_sum<<endl;
    return 0;
}