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;
}
Fall out, Codes! 