Subarray of maximum Sum of a given Array O(n^2)!!!!
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,i,j,k,sum,c_sum,left,right,current_sum;
cout<<"enter the size of array : \n";
cin>>n;
int a[n],csum[n];
for(i=0;i<n;i++)
cin>>a[i];
csum[0]=a[0];
for(i=1;i<n;i++)
csum[i]=a[i]+csum[i-1];
/*for(i=0;i<n;i++)
cout<<csum[i]<<" ";*/
sum=-1;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
current_sum=csum[j]-csum[i-1];
if(current_sum>sum)
{
sum=current_sum;
left=i;
right=j;
}
}
}
cout<<"\nMax sum will be: "<<sum<<endl;
cout<<"Subarray will be: ";
for(i=left;i<=right;i++)
cout<<a[i]<<" ";
}
Comments
Post a Comment