O(n ^ 2)

鉴于O(n ^ 2)的比较简单（就用了一个简单dp）， 我就直接上代码了。

最长上升子序列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dp[N]; // 以a[i] 为结尾的最长上升子序列的长度 
int a[i]; //给出的序列
int lis(){
    int len = 0;
    for (int i = 1; i <= n; i++){
        dp[i] = 1; // 初始化 
        for (int j = 1; j < i; j++){
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        len = max(len, dp[i]);
    }
    return len;
}

最长不下降子序列

1
2
3
4
5
6
7
8
9
10
11
12
int lis(){
    int len = 0;
    for (int i = 1; i <= n; i++){
        dp[i] = 1; 
        for (int j = 1; j < i; j++){
            if (a[j] <= a[i]) // 这里的区别
                dp[i] = max(dp[i], dp[j] + 1);
        }
        len = max(len, dp[i]);
    }
    return len;
}

最长下降子序列

1
2
3
4
5
6
7
8
9
10
11
12
int lis(){
    int len = 0;
    for (int i = 1; i <= n; i++){
        dp[i] = 1; 
        for (int j = 1; j < i; j++){
            if (a[j] > a[i]) // 这里的区别
                dp[i] = max(dp[i], dp[j] + 1);
        }
        len = max(len, dp[i]);
    }
    return len;
}

最长不上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
int lis(){
    int len = 0;
    for (int i = 1; i <= n; i++){
        dp[i] = 1; 
        for (int j = 1; j < i; j++){
            if (a[j] >= a[i]) // 这里的区别
                dp[i] = max(dp[i], dp[j] + 1);
        }
        len = max(len, dp[i]);
    }
    return len;
}

打印路径(n ^ 2)

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
void lis_path(){ // 最长上升子序列打印路径
    int len = 0,pos; //pos记录最长上升子序列的最后一个元素的下标
    for (int i = 1; i <= n; i++){
        dp[i] = 1;
        for (int j = 1; j < i; j++){
            if (a[j] < a[i] && dp[i] < dp[j] + 1){
                dp[i] = dp[j] + 1;
                path[i] = j; // path[i] 记录最长上升子序列中a[i]前的索引
                if (len < dp[i]){
                    len = dp[i];
                    pos = i;// 记录最长上升子序列的最后一个元素的下标
                }
            }
        }
       // len = max(len, dp[i]);
    }
    cout << len << "\n";
    int ans[1000];
    for (int i = len; i >= 1; i --){ // 打印路径
        ans[i] = a[pos];
        pos = path[pos];
    }
    for (int i = 1; i <= len; i++){
        cout << ans[i] << ' ';
    }
    cout << "\n";
}

O(n logn)

dp[i]存的是上升子序列长度为i的最小的一位数字
这样子dp数组一定是单调的（自己实践下）
初始时DP[1] = a[1]， 从i = 2时遍历原数列， 将每个遍历的数与DP数列的末尾进行比较， 如果大于末尾， 则把DP数列长度提1将a[i]放在DP数列的最后， 如果小于末尾那么替换掉DP数列中比a[i]大的第一个数。
结束后DP数列的长度就是LIS的长度。

举个例子：

对于序列1,5,8,3,6,7来说，当子序列为1,5,8时，遇到3时，序列已经不能继续变长了。但是，我们可以通过替换，使“整个序列”看上去更小，从而有更大的机会去变长。这样，当替换5-3和替换8-6完成后（此时序列为1,3,6），我们可以在序列末尾添加一个7了。

最长上升子序列：

1
2
3
4
5
6
7
8
9
10
11
int lis(){
    int len = 1,pos;
    dp[1] = a[1];
    for (int i = 2; i <= n; i++){
        if (a[i] > dp[len])
            dp[++len] = a[i];
        else
            *lower_bound(dp + 1, dp + len + 1, a[i]) = a[i];
    }
    return len;
}

最长不下降子序列

1
2
3
4
5
6
7
8
9
10
11
int lis(){
    int len = 1,pos;
    dp[1] = a[1];
    for (int i = 2; i <= n; i++){
        if (a[i] >= dp[len]) // here
            dp[++len] = a[i];
        else
            *upper_bound(dp + 1, dp + len + 1, a[i]) = a[i];  // here, 为什么用upper_bound呢 ， 因为咱们要替换的是大于a[i] 的数
    }
    return len;
}

最长下降子序列

1
2
3
4
5
6
7
8
9
10
11
int lis(){
    int len = 1,pos;
    dp[1] = a[1];
    for (int i = 2; i <= n; i++){
        if (a[i] < dp[len])  // here
            dp[++len] = a[i];
        else
            *lower_bound(dp + 1, dp + len + 1, a[i], greater<int>() ) = a[i];  // here
    }
    return len;
}

最长不上升子序列

1
2
3
4
5
6
7
8
9
10
11
int lis(){
    int len = 1,pos;
    dp[1] = a[1];
    for (int i = 2; i <= n; i++){
        if (a[i] <= dp[len])  // here
            dp[++len] = a[i];
        else
            *upper_bound(dp + 1, dp + len + 1, a[i], greater<int>() ) = a[i];  // here
    }
    return len;
}

打印路径（n logn）

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
void lis_path(){  // 最长上升子序列， 改成其他和上面一样改
    int len = 1;
    dp[1] = a[1];
    path[1] = 1;
    for (int i = 2; i <= n; i++){
        if (a[i] > dp[len]){
            dp[++len] = a[i];
            path[i] = len;
        }
        else{
            int cnt = lower_bound(dp + 1, dp + len + 1, a[i]) - dp;
            path[i] = cnt;
            dp[cnt] = a[i];
        }
    }
    cout << len << "\n";
    int cnt = len;
    for (int i = n; i >= 1; i--){
        if (path[i] == cnt)
            ans[cnt--] = a[i];
        if (cnt == 0)
            break;
    }
    for (int i = 1; i <= len; i++){
        cout << ans[i] << " ";
    }
    putchar(10);
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan