Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include<cmath>
#include<iostream>
#include<climits>
using namespace std;
int Maximum_Sum_Subarray(int arr[],int n) //Overall Time Complexity O(n^3)
{
int ans = INT_MIN; // #include<climits>
for(int sub_array_size = 1;sub_array_size <= n; ++sub_array_size) //O(n)
{
for(int start_index = 0;start_index < n; ++start_index) //O(n)
{
if(start_index+sub_array_size > n) //Subarray exceeds array bounds
break;
int sum = 0;
for(int i = start_index; i < (start_index+sub_array_size); i++) //O(n)
sum+= arr[i];
ans = max(ans,sum);
}
}
return ans;
}
int main(int argc, char const *argv[])
{
int arr[] = {3,-2,5,-1};
cout<<MSS(arr,4)<<"\n";
return 0;
}
@chai2champ

This comment has been minimized.

Copy link

commented Jun 25, 2014

ans = max(ans,sum) is this inbuilt function??

@mycodeschool

This comment has been minimized.

Copy link
Owner Author

commented Jul 25, 2014

Yes, max is an inbuilt function. It returns larger of two values passed as argument

@makkawysaleh

This comment has been minimized.

Copy link

commented Mar 11, 2016

I have a question how can I return the start and the end of the maximum subarray?
Like from where it begins and ends.

@08shubhamjindal

This comment has been minimized.

Copy link

commented Jun 18, 2018

@chai2champ this function is not working for large constraints

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.