Max subarray,this code gives run error

#1

#include
using namespace std;
void maxSubarray(int a[],int n){
int current_sum=0;
int max_sum=0;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
current_sum=0;
for(int k=i;k<=j;k++){
current_sum+=a[k];
}
if(current_sum>max_sum){
max_sum=current_sum;
}
}
}
cout<<max_sum<<endl;
}
int main() {
// int t[21];
int testcase;
cin>>testcase;
int a[10000];
int n;

for(int i=1;i<=testcase;i++){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
maxSubarray(a,n);

}

return 0;

}

#2

Hi @Rishabhsharm
You are facing run error because of the size of a array. It is mentioned in the question that N <= 100000 so make array as [100000] then you wont face run error but even after that your code wont get submitted as in max sub array function you are using 3 for loops due to which for large value of N your code is taking a lot of time to run. Instead you must use the following approach :

  1. Take two variables one for storing local max sum(max-ending-here) and global max sum(max-so-far).
  2. Iterate over each each element of the array say a.
    2.1 max_ending_here = max_ending_here + a[i]
    2.2 if(max_ending_here < 0)
    max_ending_here = 0
    2.3 if(max_so_far < max_ending_here)
    max_so_far = max_ending_here
  3. max-so-far is the required max sum of contiguous subarray.
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.