The Maximum Subarray

  • + 0 comments

    ` vector maxSubarray(vector arr) { if (arr.empty()) return {0,0};

    int subarr_sum=0, current_sum = 0, subseq_sum=0;
    
    for (int i : arr){
    
        current_sum = max(i, current_sum + i);
        subarr_sum = max(current_sum, subarr_sum); 
    
        if (i>0){
            subseq_sum+=i;
        }
    }
    
    if(subseq_sum==0){
        sort(arr.begin(),arr.end());
        subseq_sum = arr.back();
        subarr_sum = arr.back();
    }
    
    return {subarr_sum, subseq_sum};
    

    } `