algorithm - 该算法对于查找最长递增子序列是否正确？

Question

我收到一个未排序的数组，我需要找到最长的递增子序列。根据Wikipedia最有效的算法是 O(nlogn) 而这是 O(n) 所以我肯定在做一些愚蠢的错误

public static int[] longestAscending(int[] arr) {
        // {x /* starting index */, y /* ending index */};
        int[] max = {0, 0};
        int[] current = {0,1};

        for (int i=1; i<arr.length; i++) {
            if (arr[i-1] < arr[i]) {
                current[1]++;
                if (current[1] - current[0] > max[1] - max[0]) {
                    max[0] = current[0];
                    max[1] = current[1];
                }
            } else {
                current[0] = i;
                current[1] = i + 1;
            }
        }

        return max;
    }

Answer 1

您的算法只检测连续的子序列，不检测有间隙的子序列。例如:

1 9 2 3

此处最长的递增子序列是 1 2 3，您的算法找不到。