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