Maximum Subarray Sum question

#1

it is showing timelimit.
how to reduce time complexity
my code is
#include
using namespace std;
int main(){
int s;
cin>>s;
for(int c=0;c<s;c++){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i=i+1){
cin>>a[i];
}
int csum=0;
int maxsum=a[0];
for(int i=0;i<n;i=i+1){
for(int j=i;j<n;j=j+1){
csum=0;
for(int k=i;k<=j;k=k+1){
csum=csum+a[k];
}
if(csum>maxsum){
maxsum=csum;
}
}
}
cout<<maxsum<<endl;
}
return 0;
}

#2

Hi Gaurav, you’re getting a TLE because the approach you have used has a complexity of O(N^3). You have to try and think of a better approach. If you do not get it please tell us and we will surely tell you but first take time and try to think of an efficient logic on your own :slight_smile: .

#3

Hey Gaurav, as you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “ Ask Doubt ” section, when your doubt is resolved.