#include <iostream>
#include <cstdio>
#include<cstdlib>
#include <string>
#include <cstring>
#include <conio.h>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
int maxoverlap(vector <int> &arry, int f, int m, int l){
int m1= INT_MIN;
int s=0;
for(int i=m; i>=f; i--){
s+=arry[i];
cout<< arry[i]<< endl;
m1 = max(m1, s);
}
int m2= INT_MIN;
s=0;
for(int i=m+1; i<=l; i++){
s+=arry[i];
m2 = max(m2, s);
}
return m1+m2;
}
int maxsum(vector <int> &arry, int f, int l){
if(f==l) return arry[f];
else if(f<l){
int m = (f+l)/2;
int lmax = maxsum(arry, f, m);
int rmax = maxsum(arry, m+1,l);
int over = maxoverlap(arry,f,m,l);
return max(max(lmax,rmax),over);
}
}
int main()
{
int n;
cout << "Size of index : " ;
cin>> n;
vector <int> v;
int temp;
for(int i=0; i<n; i++){
cin>> temp;
v.push_back(temp);
}
cout << maxsum(v, 0, n-1) << endl;
return 0;
}
No comments:
Post a Comment