P19 MAXIMUM SUBSEQUENCE SUM PROBLEM （2）（分治法）

In our case, the maximum subsequence sum can be in one of three places. Either it occurs entirely in the left half of the input, or entirely in the right half, or it crosses the middle and is in both halves. The first two cases can be solved recursively. The last case can be obtained by finding the largest sum in the first half that includes the last element in the first half and the largest sum in the second half that includes the first element in the second half. These two sums can then be added together. As an example, consider the following input:

#include <stdio.h>
#include <stdlib.h>

void get_input(int arriy[], int n)
{
    int i = 0;
    for (; i < n; i++)
        scanf("%d", arriy + i);

    return;
}
int max3(int a, int b, int c)
{
    int tmp = (a>b)?a:b;
    return (tmp>c)?tmp:c;
}

void show_arriy(int arriy[], int n)
{
    int i = 0;
    for (; i < n; i++)
        printf("%d ", arriy[i]);
    printf("\n");

    return;
}

static int max_sub_sum(const int A[], int left, int right)
{
    int max_left_sum, max_right_sum;
    int max_left_border_sum, max_right_border_sum;
    int left_border_sum, right_border_sum;
    int center, i;

    if (left == right)
        if (A[left] > 0)
            return A[left];
        else
            return 0;

    center = (left + right) / 2;
    max_left_sum = max_sub_sum(A, left, center);
    max_right_sum = max_sub_sum(A ,center + 1, right);
    
    max_left_border_sum = 0;
    left_border_sum = 0;
    
    for(i = center; i >= left; i--)
    {
        left_border_sum += A[i];
        if (left_border_sum > max_left_border_sum)
            max_left_border_sum = left_border_sum;
    }

    max_right_border_sum = 0; right_border_sum = 0;
    for (i = center + 1; i <= right; i++)
    {
        right_border_sum += A[i];
        if (right_border_sum > max_right_border_sum)
            max_right_border_sum = right_border_sum;
    }

    return max3(max_left_sum, max_right_sum, max_left_border_sum + max_right_border_sum);
}

int max_subsequence_sum(const int A[], int n)
{
    return max_sub_sum(A, 0, n - 1);
}

int main (int argc, char* argv[])
{
    if (argc != 2)
    {
        fprintf(stderr, "Usage: ./a.out n\n");
        exit(1);
    }
    int n = atoi(argv[1]);
    if (n < 1)
    {
        fprintf(stderr, "Usage: ./a.out n\n");
        exit(1);
    }

    int *p_arriy = (int*)malloc(sizeof(int) * n);
    if (NULL == p_arriy)
    {
        fprintf(stderr, "stevens: malloc error!\n");
        exit(1);
    }
    get_input(p_arriy, n);
    show_arriy(p_arriy, n);
    printf("the sum is %d\n", max_subsequence_sum(p_arriy, n));
    return 1;
}