Cacher is the code snippet organizer for pro developers

// ==============================================================
// linear approach
int maximum_subarray(int A[], int N) {
    int sum_sofar = A[0], sum_final = INT_MIN;
    for(int i=1; i<N; i++) {
        sum_sofar = max(A[i], sum_sofar + A[i]);
        sum_final = max(sum_final, sum_sofar);
    }
    return sum_final;
}

// ==============================================================
// divide and conquer approach. 
int dc(int A[], int N, int low, int high) {
    if(low > high) return 0;
    
    int mid = low + (high - low) / 2;
    int sum1 = dc(A, N, low, mid-1);
    int sum2 = dc(A, N, mid+1, high);
    
    int sum_left = 0, max_left = INT_MIN;
    int i = mid;
    while(i >= low) {
        sum_left += A[i];
        max_left = max(max_left, sum_left);
        i--;
    }
    int j = mid;
    int sum_right = 0, max_right = INT_MIN;
    while(j <= high) {
        sum_right += A[j];
        max_right = max(max_right, sum_right);
        j++;
    }
    int sum_cross = max_left + max_right - A[mid];
    return max(sum_cross, max(sum1, sum2));
}

int max_subarray_dc(int A[], int N) {
    return dc(A, N, 0, N-1);
}