Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Last active October 13, 2023 19:48
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 8 You must be signed in to fork a gist
  • Save mycodeschool/447854ea1844b1b42cd3 to your computer and use it in GitHub Desktop.
Save mycodeschool/447854ea1844b1b42cd3 to your computer and use it in GitHub Desktop.
#include<cmath>
#include<iostream>
#include<climits>
using namespace std;
int Maximum_Sum_Subarray(int arr[],int n) //Overall Time Complexity O(n^2)
{
int ans = INT_MIN;
for(int start_index = 0;start_index < n; ++start_index) //O(n)
{
int sum = 0;
for(int sub_array_size = 1;sub_array_size <= n; ++sub_array_size) //O(n)
{
if(start_index+sub_array_size > n) //Subarray exceeds array bounds
break;
sum+= arr[start_index + sub_array_size - 1]; //Last element of the new Subarray
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;
}
@eibo
Copy link

eibo commented Feb 27, 2017

Why do you have MSS on line 26?

@allisonsampaio
Copy link

is the function call Maximum_Sum_Subarray

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment