4

我正在编写代码来查找 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;
}
4

5 回答 5

6

有点离题，但这个问题以解决它的最佳方法而闻名（在线性时间内）。您可以完全从规范中派生代码。

首先，正式定义问题：

给定：整数数组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;
}
于 2013-09-10T09:32:51.290 回答
4

您的代码中存在一些未定义行为的问题：

第一个是您传递9as highwhich 将用于索引八元素数组的第十个元素。这将是第十个，因为在cross_max你循环 whilei <= high中，所以你会索引arr[9]。请记住，数组索引是从零到大小减一（因此您可以为数组索引 from 0to 7）。超出范围的索引将包含未定义（即随机）的值。

第二个问题是您从cross_max. 当您使用返回的指针时，这将导致未定义的行为。局部变量只在它们被声明的范围内有效，当函数返回时，局部变量使用的内存区域将被回收并用于下一个函数。

于 2013-09-10T07:48:21.950 回答
1

这是获得最大值的帮手。

int maxcmp(int a, int b) {
    return a >= b ? a : b;
}

这个想法是当你迭代数字时，你把它们加在一起。如果到目前为止您的 cur_sum 小于 0，则您消除到目前为止的所有数字。因为在该点之后添加负值不会增加其余 nums 的总和。

int maxSubArray(int* nums, int numsSize){
    int maxSoFar = nums[0], 
    cur_sum = 0;
    for(int i = 0; i < numsSize; i++) {
        if (cur_sum<0){
            cur_sum=0;
        }
        cur_sum=cur_sum+nums[i];
        maxSoFar=maxcmp(maxSoFar,cur_sum);
    }
    return maxSoFar;
}`enter code here`
于 2022-02-12T01:33:33.700 回答
0

该算法效率不高。时间复杂度为o(n^2)。这是一个动态规划算法，即o(n).

/*************************************************************************
    > File Name: subarray.cpp
    > Author: luliang
    > Mail: lulyon@126.com 
    > Created Time: 2013/09/10 Tuesday 15:49:23
 ************************************************************************/

#include <stdio.h>

typedef struct {
    int low;
    int high;
    int sum;
}DPInfoType;


int main()
{
    int arr[8] = {1,1,2,-2,3,3,4,-4};
    const int n = sizeof(arr) / sizeof(arr[0]);

    DPInfoType dp[n];
    dp[0].low = 0;
    dp[0].high = 0;
    dp[0].sum = arr[0];

    for(int i = 1; i < n; ++i) {
        if(dp[i - 1].sum > 0) {
            dp[i].low = dp[i - 1].low;
            dp[i].high = i;
            dp[i].sum = dp[i - 1].sum + arr[i];
        }
        else {
            dp[i].low = i;
            dp[i].high = i;
            dp[i].sum = arr[i];
        }
    }

    int max_index = 0;
    for(int i = 1; i < n; ++i) {
        if(dp[max_index].sum < dp[i].sum) max_index = i;
    }

    printf("\n Maximum sum = %d\n", dp[max_index].sum);
    printf("\n low = %d\n", dp[max_index].low);
    printf("\n high = %d\n", dp[max_index].high);

    return 0;
}
于 2013-09-10T08:06:37.813 回答
0

如前所述，在您的代码中使用指针是不合适的。这段代码对我有用。

#include <stdio.h>
#define INF 1000000

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

int findMaxCrossingSubarray (int arr[], int low, int mid, int high, int *start, int *end)
{
    int i, left, right;
    int max_left, max_right;
    int left_sum = -INF;   
    int sum = 0;
    for (i = mid; i >= 0; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
            max_left = i;
        }
    }
    int right_sum = -INF;
    sum = 0;
    for (i = mid + 1; i <= high; i++) {
        sum += arr[i];
        if (sum > right_sum) {
           right_sum = sum;
           max_right = i;
        }
    }
    *start = max_left;
    *end = max_right;
    return left_sum + right_sum;
}

int findMaxSubarray (int arr[], int low, int high, int *start, int *end) 
{
    if (low == high) 
        return arr[low];

    int mid = (high - low)/2 + low;
    int start1, start2, start3;
    int end1, end2, end3;
    // initialization of start and end for terminal cases.
    start1 = start3 = low;
    start2 = mid + 1;
    end1 = mid;
    end2 = end3 = high;
    int sum1 = findMaxSubarray(arr, low, mid, &start1, &end1);
    int sum2 = findMaxSubarray(arr, mid + 1, high, &start2, &end2);
    int sum3 = findMaxCrossingSubarray(arr, low, mid, high, &start3, &end3);
    int res =  max(max(sum1, sum2), sum3);
    if (res == sum1) {
        *start = start1;
        *end = end1;
    }
    if (res == sum2) {
        *start = start2;
        *end = end2;
    }
    if (res == sum3) {
        *start = start3;
        *end = end3;
    }
    return res;
}

int main(int argc, char const *argv[])
{
    int size, i, item, result;
    printf("Enter the size of array: ");
    scanf("%d",&size);
    int arr[size];
    printf("Enter the array:\n");
    for (i = 0; i < size; ++i) {
        scanf("%d",&item);
        arr[i] = item;
    }
    int start = 0, end = size-1;
    result = findMaxSubarray(arr, 0, size-1, &start, &end);
    printf("Result: %d, start: %d and end: %d.\n", result, start, end);
    return 0;
}
于 2015-05-21T20:27:10.923 回答