Longest Increasing Subsequence -- Linear Time Solution?

Question

We can use a stack to keep recording increasing subsequences while iterating the array. The run time is linear because each element enters and leaves the stack once.

If we want to output the actual sequence instead of its length, we can record the starting index, and then find all elements after it with greater values.

Does this linear time algorithm work?

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

I tried and it gives correct results. But it's a little hard to say whether it's O(n) or not. Wikipedia and other sources all mark this problem as O(nlogn) — zhe, May 01 '14 at 16:36
Maybe you're confusing substring (contiguous) with subsequence (does not need to be contiguous) — Niklas B., May 01 '14 at 17:19
@NiklasB. This wont give the longest increasing substring also. — HelloWorld123456789, May 01 '14 at 17:26

HelloWorld123456789 · Answer 1 · 2014-05-01T16:47:15.477

1

No. The algorithm you've written is not correct.

Consider the test case: 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

But in reality the answer should be 3.

edited May 01 '14 at 16:47

answered May 01 '14 at 16:39

HelloWorld123456789

5,299
3
23
33

`But in reality the answer should be 3.` - how so? – 500 - Internal Server Error May 01 '14 at 17:17
@500-InternalServerError `15,20,25` – HelloWorld123456789 May 01 '14 at 17:17
Ah, I thought it had to be unbroken. – 500 - Internal Server Error May 01 '14 at 17:21
@500-InternalServerError Subsequence, not subarray. – HelloWorld123456789 May 01 '14 at 17:22
Good test case! I thought every increasing subsequence enters the stack, but that's not the case. – zhe May 01 '14 at 18:20
@zhe This problem can be solved in `O(nlogn)` though. See [this](http://stackoverflow.com/a/7614385/1519469). – HelloWorld123456789 May 01 '14 at 18:26

Longest Increasing Subsequence -- Linear Time Solution?

1 Answers1