FIND THE SUM OF THE MAXIMUM SUBARRAY.
Input Format
First line contains N value denoting number of integers
Next line contains N integers seperated by a space.
Constraints
1<=N<1000000
-10000<=a[i]<=10000
Output Format
A single integer denoting sum of the maximum sub array
Sample Input 0
8
-1 2 4 -3 5 2 -5 2
Sample Output 0
10#include<iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int cmp(void const *a,void const *b)
{
return *(int *)a- *(int *)b;
}
int max(int *a,int n)
{
int i,maxso=0,max_end=0;
for(i=0;i<n;i++)
{
max_end=max_end+a[i];
if(max_end<0)
max_end=0;
if(maxso<max_end)
maxso=max_end;
}
return maxso;
}
int main()
{
int *a;
int n;
cin>>n;
a=new int[n];
int *b;
b=new int[n];
int f=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
b[i]=a[i];
if(a[i]>0)
f=f+1;
}
int max_sum=max(a,n);
qsort(b,n,sizeof(int),cmp);
int d=0,sum=0;
for(int i=n-1;i>=0;i--)
{
sum=sum+b[i];
if(sum>d)
d=sum;
}
if(n==1||f==0)
{
d=b[n-1];
max_sum=b[n-1];
}
cout<<max_sum;
return 0;
}
