-4

我有一个练习要解决：“编写一个高效的 C 程序，以找到一维整数数组中连续子数组的最大和。数组的连续子数组定义为任何连续集合中的元素序列在数组中有效的索引。

让我们以数组 {5,-3, 4} 为例。可能的连续子数组组合是 {5}、{-3}、{4}、{5,-3}、{-3,4} 和 {5,-3,4}。请注意，{5,4} 不是有效的子数组，因为 5 和 4 的索引不连续。连续子数组 {5,-3,4} 的最大和为 6。”

我试图解决它，但我意识到我什至不明白这个问题，因为如果我有一个包含 5 个不同值的数组，结果应该是 10，而我会说 15（5 个不同元素 + 1个整体 + 4 个元素如果 2 乘 2 + 3如果 3 乘 3 + 2如果 4 乘 4）。

在尝试（用 C 语言）对其进行编码之前，我想知道是否有人可以帮助我理解问题本身。

4

1 回答 1

0

这就是我解决问题的方法。这不一定是最佳解决方案，但我相信它应该有效。

考虑数组：{1, -2, 3, 5, -4} 并考虑如何手动编写所有子数组：

  1. 从 5 元素数组开始：{1, -2, 3, 5, -4} 总和：3
  2. 接下来写出 4 元素数组：
    {1, -2, 3, 5} sum of: 7
    {-2, 3, 5, -4} sum of: 2
  3. 继续 3 元素数组：
    {1, -2, 3} sum of: 2
    {-2, 3, 5} sum of: 6
    {3, 5, -4} sum of:4
  4. 现在是 2 元素数组：
    {1, -2} sum of: -1
    {-2, 3} sum of: 1
    {3, 5} sum of: 8
    {5, -4} sum of: 1
  5. 最后，1 元素数组：
    {1} 总和：1
    {-2} 总和：-2
    {3} 总和：3
    {5} 总和：5
    {-4} 总和：-4

看起来最大的和是8。

您应该在这里看到一个模式，我从数组的长度开始，在本例中为 5，然后将其减一，直到处理单元素数组。我还从数组的第零个元素开始，并尝试在给定长度的情况下创建一个有效的数组。例如，如果我使用四元素数组，从数组元素 0 开始，它可以通过 array[0] -> array[3] 和 array[1]->array[4] 创建一个子数组（这是数组切片，某些语言（如 Python）具有执行数组切片的明确表示法，而 C 没有）。生成每个切片后，对元素求和，完成后查找最大值。

现在，我会编写这样的代码

int main(void)
{
    int array[] = {1, -2, 3, 5, -4};
    int max = -1;                         // will hold largest sum
    int len = sizeof(array)/sizeof(int);  // C-idiom to find length of array

    for(int slen = len; slen > 0; slen--)           // loop for length of sub-arrays
    {
        for(int jdx = 0; jdx+slen <= len; jdx++)   // looping over elements in original array
        {
             int temp = calcSum(array, jdx, slen);
             if(temp > max)
                 max = temp;

        }
    }
    printf("maximum sum of sub-array is: %d\n", max);
}

现在剩下的就是编写calcSum函数了。它需要三个参数——第一个是原始数组，第二个是子数组的开始位置，这是子数组的长度。

int calcSum(int* array, int start, int len)
{
    int    sum = 0;
    printf("[%d:%d]: {", start, start+len);
    for(int ndx = 0; ndx < len; ndx++)
    {
        printf("%d,", array[start+ndx]);
        sum = sum + array[start+ndx];
    }

    printf("} the sum is %d\n", sum);
    return sum;
}

我在里面撒了一些 printf，这样你就可以看到程序循环时发生了什么。我的切片符号是 [start:length] 所以 [1:3] 是从索引 1 开始的数组，长度为 3（即数组 [1]、数组 [2]、数组 [3]）。

将上述内容编译为gcc -std=c99 -pedantic -Wall test.c -o temp并执行，将产生：

D:\Users\******\GNUHome>temp.exe
[0:5]: {1,-2,3,5,-4,} the sum is 3
[0:4]: {1,-2,3,5,} the sum is 7
[1:4]: {-2,3,5,-4,} the sum is 2
[0:3]: {1,-2,3,} the sum is 2
[1:3]: {-2,3,5,} the sum is 6
[2:3]: {3,5,-4,} the sum is 4
[0:2]: {1,-2,} the sum is -1
[1:2]: {-2,3,} the sum is 1
[2:2]: {3,5,} the sum is 8
[3:2]: {5,-4,} the sum is 1
[0:1]: {1,} the sum is 1
[1:1]: {-2,} the sum is -2
[2:1]: {3,} the sum is 3
[3:1]: {5,} the sum is 5
[4:1]: {-4,} the sum is -4
maximum sum of sub-array is: 8

注意我在 Windows 7 Professional 上使用 gcc 版本 4.8.3（来自 mingw）编译了这个。

于 2016-01-31T19:18:44.257 回答