arrays - 为什么最大和子数组是暴力 O(n^2)？

Question

maximum subarray sum是计算机科学中的著名问题。

至少有两种解决方案:

1. 蛮力法，找出所有可能的子数组，并找出最大值。
2. 使用 Kadane's Algorithm 的变体在遍历数组的第一遍时计算全局最大值。

在视频中 tutorial作者提到的暴力方法是O(n^2)，阅读another answer一个人认为是 O(n^2)，另一个人认为是 O(n^3)。

蛮力是 O(n^2) 还是 O(n^3)？更重要的是，您能否说明您对蛮力方法执行了哪些分析才能知道它是 O(?)？

Answer 1

好吧，这取决于力的强度。

如果我们生成所有 (i, j): i <= j对并计算它们之间的和，它是O(n^3) :

....
for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++) {
        int sum = 0;
        for (int k = i; k <= j; k++)
            sum += a[k];
        if (sum > max)
            max = sum;
    }

如果我们从所有位置开始并计算运行总和，则为 O(n^2) :

....
for(int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = i; j < n; j++) {
        sum += a[j];
        if (sum > max)
            max = sum;
    }
}