Not very short, but O(n) time solution


#1

Here we are traversing the array once.

vector<int> Solution::maxset(vector<int> &A) {

    int start = 0;
    int end = -1;
    long int max = 0;
    int ms = 0 ;
    int me = -1;
    long int sum = 0;
    for(int i=0; i< A.size();i++){
        if(A[i] >= 0){
            sum+=A[i];
            end = i;
        }
        else{
            if(max < sum){
                max = sum;
                ms = start;
                me = end;
            }
            else if(max == sum){
                if((end-start) > (me - ms)){
                    max = sum;
                    ms = start;
                    me = end;
                }
                else if((end-start) == (me - ms)){
                    if(start < ms){
                        max = sum;
                        ms = start;
                        me = end;
                    }
                }
            }
            start = i+1;
            sum = 0;
        }
    }
    if(max < sum){
                max = sum;
                ms = start;
                me = end;
    }
    
    vector<int> result;
    if(me == -1)
        return result;
    copy(A.begin()+ms,A.begin()+me+1, back_inserter(result));
    return result;
}