java - 用于处理列表的所有连续子序列的简单代码的算法复杂度 : n^2 or n^3?

Question

我正在学习考试，发现了这个问题:

我无法确定复杂性，我认为它是 O(n²) 或 O(n³)，我倾向于 O(n ³)。
谁能告诉我它是什么以及为什么？

我认为它是 O(n²) 是因为在 j 循环中， j = i 给出了一个三角形，并且然后 k 循环从 i + 1 到 j，我认为这是三角形的另一半。

public static int what(int[] arr)
{
    int m = arr[0];
    for (int i=0; i<arr.length; i++)
    {
        for (int j=i; j<arr.length;j++)
        {
            int s = arr[i];
            for (int k=i+1; k<=j; k++)
             s += arr[k];
            if (s > m)
             m = s;
        }
    }
    return m;
}

如果你能告诉我它是做什么的？

我想它会返回正整数或数组中最大整数的加法。
但是对于像 {99, -3, 0, 1} 这样的数组，它会返回 99，我认为这是因为它有问题。如果不是，我不知道它做了什么:

{99, 1} => returns 100
{-1, -2, -3} => return -1
{-1, 5, -2} => returns 5
{99, -3, 0, 1} => returns 99 ???

Answer 1

您可以有条不紊地进行，使用 Sigma 表示法，以获得增长复杂度的顺序: