Welcome to FutureAppLaboratory

v=（*＾ワ＾*）=v

Longest Increasing Subsequence

| Comments

Introduction

In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible.

For example, a longest increasing subsequence of 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 is 0, 2, 6, 9, 11, 15.

An O(N2) Solution

We define a $dp$ table, which $dp[i]$ is the length of a longest subsequence which ends at $inputs[i]$.

For each $inputs[i]$, we search every inputs before it, and choose the longest possible $dp$ value from them, fill it in $dp[i]$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

private int[] inputs = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
private int[] dp = new int[128];

public int solution() {
    for (int i = 0; i < dp.length; i++) { dp[i] = 0; }
    dp[0] = 1;

    for (int i = 1; i < inputs.length; i++) {
        int longest = 1;
        for (int j = 0; j < i; j++) {
            if (inputs[i] > inputs[j]) {
                longest = Math.max(longest, dp[j] + 1);
            }
        }
        dp[i] = longest;
    }
    return dp[inputs.length - 1];
}

An O(N*Log(N)) Solution

We define a $seq$ table, which $seq[i]$ is the ending number of subsequence whose length is $i$.

Note that, $seq$ is always in increasing order.

Because if these exist $i < j$ and $seq[i] > seq[j]$, which means a longer subsequence end with a smaller number.

Then we could generate a new subsequence, which length is $i$, by removing $j - i$ numbers from tail of $j$-length subsequence. The ending number of the new subsequence will be smaller than $seq[i]$.

Therefore, we can use binary search in each iteration, to find the largest $seq[k]$ which is smaller than $inputs[i]$. If $k$ can be found ($k > -1$), then we update the number stored in $seq[k]$ with $inputs[i]$ if $inputs[i] < seq[k]$.

This yields an O(N*Log(N)) solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

private int[] seq = new int[128];

public int solution2() {
    for (int i = 0; i < seq.length; i++) { seq[i] = Integer.MAX_VALUE; }

    int res = Integer.MIN_VALUE;
    for (int i = 0; i < inputs.length; i++) {
        int longest = 1;
        int bestSeqLength = binarySearch(seq, 0, i, inputs[i]);
        if (bestSeqLength > -1) {
            longest = bestSeqLength + 1;
        }
        seq[longest] = Math.min(seq[longest], inputs[i]);
        res = Math.max(res, longest);
    }
    return res;
}

public int binarySearch(int[] array, int begin, int end, int target) {
    int s = begin;
    int t = end;
    int m = s;
    int result = -1; // !!!
    while (s <= t) {
        m = (s + t) / 2;
        if (array[m] < target) {
            s = m + 1;
            result = m; // result index, which array.get(result) is most close to & less than target
        } else if (array[m] == target) {
            return m;
        } else {
            t = m - 1;
        }
    }
    return result;
}

Comments