sundeepblue
4/12/2014 - 9:31 PM

maximum subarray sum. Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

maximum subarray sum. Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

max_subarray.cpp
content_copyfile_download
int largest_sum_subaray(vector<int>& A) {
    int max_final = A[0], max_endhere = A[0];
    for(int i=1; i<n; ++i) {
        max_endhere = max(A[i], max_endhere + A[i]);
        max_final = max(max_final, max_endhere);
    }
    return max_final;
}