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

@chai2champ chai2champ commented Jun 25, 2014

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

@mycodeschool

This comment has been minimized.

Copy link
Owner Author

@mycodeschool mycodeschool 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

@makkawysaleh makkawysaleh 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

@08shubhamjindal 08shubhamjindal 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