c - 查找最大总和连续子数组

Question

我正在编写代码以在 C 中查找最大总和连续子数组。根据我的逻辑似乎没问题，但输出仍然不正确。请查看代码。该算法将一个较大的数组分成 2 个子数组。然后它通过检查左数组、右数组以及包含中点的数组来检查最大和子数组(它将从中点检查左右，然后返回包含中点的最大和子数组)。

int* cross_max(int arr[], int low, int mid, int high)
{
    int left_max, left_sum = -2000;
    int sum = 0;
    int i;
    for(i=mid; i>=low;i--)
    {
        sum = sum + arr[i];
        if(sum > left_sum)
        {
            left_sum = sum;
            left_max = i;
        }
    }


    int right_max, right_sum = -2000;

    for(i=mid+1; i<=high;i++)
    {
        sum = sum + arr[i];
        if(sum > right_sum)
        {
            right_sum = sum;
            right_max = i;
        }
    }

    // 0 - sum
    // indices - 1,2

    int temp_arr[3] = {0,0,0};
    temp_arr[0] = left_sum + right_sum;
    temp_arr[1] = left_max;
    temp_arr[2] = right_max;

    int *p = temp_arr;

    printf("\n Maximum sum = %d\n",*p);
    printf("\n low = %d\n",*(p+1));
    printf("\n high = %d\n",*(p+2));    

    return p;

}


int* find_max(int arr[], int low, int high)
{
    int temp_arr[3] = {0,0,0};
    if(low == high)
    {
        temp_arr[0] = arr[low];
        temp_arr[1] = low;
        temp_arr[2] = low;

        int *q = temp_arr;
        return q;
    }

    int mid = (low + high)/2; 

    int* a1 =  find_max(arr,low,mid);
    int* a2 =  find_max(arr,mid+1,high);
    int* a3 =  cross_max(arr,low,mid,high);

    if (*a1 > *a2 && *a1 > *a3)
        return a1;

    else if (*a2 > *a1 && *a2 > *a3)
        return a2;

    else
        return a3;

}


int main()
{
    int arr[8] = {1,1,2,-2,3,3,4,-4};

    int *point = find_max(arr,0,7);

    printf("\n Maximum sum = %d\n",*point);
    printf("\n low = %d\n",*(point+1));
    printf("\n high = %d\n",*(point+2));    
    return 0;
}

Answer 1

稍微偏离主题，但这个问题以解决它的最佳方法(线性时间)而闻名。您可以完全从规范中导出代码。

首先，正式定义问题:

给定:整数数组A[0, N)

必需:

max(0 <= p <= q <= N : sum(p, q)) 
    where sum(p, q) = sum(p <= i < q : A[i])

方法:

让X(n) = max(0 <= p <= q <= n : sum(p, q)) , 然后我们需要找到 X(N) .我们通过归纳来做到这一点:

X(0) = max(0 <= p <= q <= 0 : sum(p, q))
     = sum(0, 0)
     = sum(0 <= i < 0 : A[i])
     = 0

和

X(n+1) = max(0 <= p <= q <= n+1 : sum(p, q))
       = max(max(0 <= p <= q <= n : sum(p, q)), max(0 <= p <= n+1 : sum(p, n+1)))
       = max(X(n), Y(n+1))

哪里Y(n) = max(0 <= p <= n : sum(p, n)) .我们现在还确定 Y(n)通过归纳法:

Y(0) = max(0 <= p <= 0 : sum(p, 0))
     = sum(0, 0)
     = 0

和

Y(n+1) = max(0 <= p <= n+1 : sum(p, n+1))
       = max(max(0 <= p <= n : sum(p, n+1)), sum(n+1, n+1)))
       = max(max(0 <= p <= n : sum(p, n)) + A[n], 0)
       = max(Y(n) + A[n], 0)

代码:

使用上面的分析，代码很简单。

int arr[8] = {1,1,2,-2,3,3,4,-4};
int N = 8;

int x = 0;
int y = 0;

for (int n = 0; n < N; n++) {
    y = max(y + arr[n], 0);
    x = max(x, y);
}

printf("Maximum sum = %d\n", x);

与

int max(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}