algorithm - 最長増加サブシーケンス -- 線形時間ソリューション?

Question

スタックを使用して、配列を反復しながら増加するサブシーケンスを記録し続けることができます。各要素はスタックに 1 回出入りするため、実行時間は線形です。

その長さではなく実際のシーケンスを出力したい場合は、開始インデックスを記録し、その後のすべての要素をより大きな値で見つけることができます。

この線形時間アルゴリズムは機能しますか?

    public int longestIncreasingSubsequence(int[] seq) {
    int longest = 0;
    int curSize = 0;

    LinkedList<Integer> stack = new LinkedList<Integer>();

    for (int i : seq) {
        while (!stack.isEmpty() && i <= stack.get(0)) {
            stack.removeFirst();
            curSize--;
        }
        stack.addFirst(i);
        curSize++;
        if (curSize > longest) {
            longest = curSize;
        }
    }

    return longest;
}