Самая длинная возрастающая подпоследовательность - решение с линейным временем?

Question

Мы можем использовать стек, чтобы продолжать записывать увеличивающиеся подпоследовательности, перебирая массив. Время выполнения является линейным, потому что каждый элемент входит и выходит из стека один раз.

Если мы хотим вывести фактическую последовательность вместо ее длины, мы можем записать начальный индекс, а затем найти все элементы после него с большими значениями.

Этот алгоритм линейного времени работает?

    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;
}

Answer 1

Нет. Алгоритм, который вы написали, неверен.

Рассмотрим контрольный пример: 15,20,12,25

After two pushes:
stack: 20,15
curSize: 2
longest: 2

In comes 12. So two pops.
curSize: 0

12 pushed:
stack: 12
curSize: 1
longest: 2

25 pushed:
stack: 25,12
curSize: 2
longest: 2 //so gives answer 2

Но на самом деле ответ должен быть 3.