寻找最大和的连续子数组

Question

我正在编写一段代码来寻找C语言中的最大和连续子数组。按照我的逻辑似乎没有问题，但是输出结果仍然不正确。请查看代码。该算法将一个更大的数组分成两个子数组。然后它通过检查左数组、右数组以及包含中点的数组来查找最大和的子数组（它会从中点向左和向右检查，然后返回包含中点的最大和子数组）。

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;
}

- tryingToLearn

---

find_max(arr,0,9); 应为 find_max(arr,0,8);，其中 high 为 8，没有 **?**。 - Grijesh Chauhan

这个算法与两个嵌套的for循环有何不同？它们都是O(n^2)。 - lulyon

是的，9 是错误的。7 才是正确的索引。这里忘记编辑了。 - tryingToLearn

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;
}

- Vincent van der Weele

---

这段代码也可以通过观察得出较不正式的推导，即对于一个解，解的每个前缀也必须具有非负和。这就解释了步骤“y = max(y + arr[n], 0);”。 - micans

Answer 2

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

首先是在将9作为high传递，这将用于索引八元素数组的第十个元素。之所以会出现第十个元素，是因为在cross_max中，你循环时使用了 i <= high，因此将索引arr[9]。请记住，数组索引是从零到大小减一（因此对于您的数组，可以从0到7索引）。越界的索引将包含未定义（即随机）值。

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

- Some programmer dude

---

是的，9是错误的。7才是正确的索引。这里忘记编辑了。 其次，指针指向固定的内存位置，那么为什么代码的行为会是未定义的呢？ - tryingToLearn

@akshay 局部变量，包括数组（例如cross_max中的temp_arr），仅在它们声明的函数内部的作用域范围内。你不能从函数外部使用它，因为一旦函数返回，它将不再存在。从技术上讲，它位于栈上，编译器在进入函数时基本上将局部变量推入堆栈，并在返回时弹出它们。 - Some programmer dude

Joachim Pileborg，我是编程新手，所以我的问题可能看起来很傻，请您耐心等待。我的意思是，temp_arr是局部的。但是在我将其地址分配给指针p之后，即使函数作用域结束，这个指针也会保留值吗？ - tryingToLearn

@akshay 是的，它会，但是当函数返回指向数组的指针时，该指针所指向的"消失"了，因此该指针不能再使用。而且，在下一次调用任何函数时，该内存很可能会被覆盖。 - Some programmer dude

我想我现在理解了这个概念。由于我正在使用相同的指针，所以即使该指针指向不同的内存位置，先前的值也将丢失。 - tryingToLearn

Answer 3

这是一个获取最大值的辅助工具。

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

这个想法是在遍历nums时将它们相加。如果当前的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`

- Yilmaz

Answer 4

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

#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;
}

- ritesh4302

Answer 5

这个算法并不是非常高效。时间复杂度为o(n^2)。这里有一个动态规划算法，时间复杂度为o(n)。

/*************************************************************************
    > File Name: subarray.cpp
    > Author: luliang
    > Mail: [e-mail] 
    > 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;
}

- lulyon