第二种算法是如何变得比第一种算法更有效的，第二种算法中子阵列的右侧是如何移动的？

提问者：小点点

第二种算法是如何变得比第一种算法更有效的，第二种算法中子阵列的右侧是如何移动的？

问题-给定一个n个数组，我们的任务是计算最大子数组和，即数组中连续值序列的最大可能和。当数组中可能有负值时，问题就很有趣了。数组={-1,2,4,-3,5,2,-5,2}。

第一种算法-

int best = 0;
    for (int a = 0; a < n; a++) {
        for (int b = a; b < n; b++) {
            int sum = 0;
            for (int k = a; k <= b; k++) {
                sum += array[k];
            }
        best = max(best,sum);
        }
    }
cout << best << "\n";

第二种算法-

int best = 0;
    for (int a = 0; a < n; a++) {
        int sum = 0;
        for (int b = a; b < n; b++) {
            sum += array[b];
            best = max(best,sum);
        }
    }
cout << best << "\n";

这是它在书中说的--从算法1中去掉一个循环，就很容易让算法1变得更高效。这可以通过在子数组右端移动时同时计算和来实现。

第二种算法中子数组的右端是如何移动的，有人能给我解释一下吗？

共1个答案

匿名用户

第一个版本对从indexa到indexb的子数组的所有子数组和进行强力比较，我们将这些子数组称为sumssubsum(a,b)。

第二个版本也是蛮力的，但使用了subsum(a,b+1)==subsum(a,b)+array[b+1]。

换句话说：要知道第一个10元素的和，可以使用前面计算的第一个9元素的和。如果你想用笔和纸解决问题，这将是显而易见的，但第一个版本没有做到这一点。相反，第一个版本对于a和B的所有组合都有两个嵌套循环，并且总是以新的sum=0开头，这是相当浪费的。

只考虑第一个版本的外部循环：

for (int a = 0; a < n; a++) {
    for (int b = a; b < n; b++) {
        int sum = 0;
        // ...
    }
}

这里//...计算子和（a,b）。

在第二个版本中：

int best = 0;
for (int a = 0; a < n; a++) {
    int sum = 0;
    for (int b = a; b < n; b++) {
        sum += array[b];
        best = max(best,sum);
    }
}

外循环负责在不同的“左端”启动子数组。内圈“移动”了“端点”。最内部的循环体计算subsum(a,b)并且内部循环的下一次迭代使用上面的关系“移动”b到下一个索引来计算subsum(a,b)==subsum(a,b-1)+array[b]。因为A是固定在内循环中的，所以作者说的是“移动右端”。