Tuesday, June 14, 2016

MAXIMUM SUM IN A SUBARRAY WITH ARRAY

#include <iostream>
#include <cstdio>
#include<cstdlib>
#include <string>
#include <cstring>
#include <conio.h>
#include <algorithm>
#include <climits>
#include <vector>

using namespace std;

int arry[100];

int maxoverlap(int f, int m, int l){
int m1= INT_MIN;
    int s=0;
    for(int i=m; i>=f; i--){
        s+=arry[i];
        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(int f, int l){
if(f==l) return arry[f];
    if(f<l){
        int m = (f+l)/2;
        int lmax = maxsum(f,m);
        int rmax = maxsum(m+1,l);
        int over = maxoverlap(f,m,l);
        return max(max(lmax,rmax),over);
    }
}


int main()
{
    int n;
cout << "Size of index : " ;
    cin>> n;
    for(int i=0; i<n; i++){
        cin >> arry[i];
    }
 
    cout << maxsum(0, n-1) << endl;

    return 0;
}


No comments:

Post a Comment