Maximum subarray sum

#1

In the method where we solve the maximum subarray sum problem in O(n^2) ,we use the cummalative array…

I give input : {1,2,3,4}

get cummalative array as:-{1,3,6,10}

but get the maximum subarray=9…

In this method ,it is not consider the a[0] position element ??

#2

hey @aattuull, can you share the code saved in coding blocks ide, for which you are taking about,

#3

my code show different outputs
different output in coding block online ide
different output on codeblock ide

and both output result are incorrect

#4

//maximum subarray sum with O(n^2) time complexity

#include
using namespace std;
int main()
{
int n,arr[1000];
int cum_sum[]={0}; //define a cumalative array

cout<<"enter the size of an array \n";
cin>>n;

cout<<"enter array element values \n";
cin>>arr[0];
cum_sum[0]=arr[0];                            

for(int i=1;i<n;++i)
{
    cin>>arr[i];                                 //insert element in array
    cum_sum[i]=cum_sum[i-1]+arr[i];               //and calculate cummalative array values
}

cout<<"array contain\t";
for(int i=0;i<n;++i)
    cout<<arr[i]<<",";

int maxx=0,sum;                              //maxx store the maximum subarray sum

int left,right;                              

for(int i=0;i<n;i++)
{
    for(int j=i;j<n;j++)
    {
        sum=0;
        sum=cum_sum[j] - cum_sum[i-1];         //main logic 
        if(sum>maxx)
        {
            maxx=sum;
            left=i;
            right=j;
        }
    }
}
cout<<"\n maximum subarray sum is :\n"<<maxx;
return 0;

}

#5

hey @aattuull, outer for loop should start with int i=1 instead of int i=0, so that you able to find cum_sum[i-1] when i=1

#6

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.