$$\color{Red}{最长上升子序列-普通版+二分贪心单调栈版}$$

我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

方法一：动态规划

1.算法细节

• 本题和kmp区分的依据是：kmp是连续子串，这题是不连续子序列

• 状态表达式存储的是什么？

dp[i]存储的是以i为结尾的最大上升子序列长度，属性为max。

• 那么如何构造状态方程？

不难想到，我们只需要迭代查询当前a[i]之前的1 ——> i - 1 的所有a[j]值，如果当前元素大于它，势必可以与它构造一个上升序列，dp[i] = dp[j] ++.我们只需要在不断的赋值过程中，将最大的值最后赋给当前d[i]即可

为什么是f[i] = max(f[i], f[j]+1]——》此时凭什么认为a[i]大于a[j]就是更大？——》还没彻底理解f[i]的实际含义，f[i]代表的是从第一个到第i个数字的集合最大的上升子序列，当a[i]大于a[j]说明至少对于以a[j]为倒数第二元素，a[i]为倒数第一元素的上升子序列，我们将i 之前每个遍历，即可得到以a[i]结尾的那个最长上升子序列

其实这道题应该给状态方程初始化f[i] = 1, 意味着最开始以这个数字结尾的数字只有它本身，也就是序列长度已经为1了。
但是为了快，也可以不初始化，最终答案的变量自增1输出也可，相当于把未计算的第一个数字的序列长度加上。

java

import java.util.*;

public class Main{
    static int N = 1010;
    static int a[] = new int [N];
    static int f[] = new int [N];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=1; i<=n; i++) a[i] = sc.nextInt();
        Arrays.fill(f, 1);

        int res = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<i; j++)
                if (a[i] > a[j])
                    f[i] = Math.max(f[i], f[j] + 1);
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }
}

python3

N = 1010
f = [1] * N
n = int(input())
a = [0] + [int(x) for x in input().split()]

res = 0
for i in range(1, n+1):
    for j in range(1, i):
        if a[j] < a[i]:
            f[i] = max(f[i], f[j] + 1)
    res = max(res, f[i])

print(res)

C++

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[N], dp[N];
int n;

int main()
{
    cin >> n;
    int res = 1;

    for(int i=1; i<=n; i++) 
    {
        cin >> a[i];
        dp[i] = 1;//以i结尾最小的上升子序列长度
        for(int j=1; j<i; j++)  
            if(a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);//精髓（试着从头去理解其记录逻辑）
        res = max(res, dp[i]);
    }
    cout << res << endl;
    return 0;
}

方法二：单调栈 + 二分搜索 + 贪心

1.算法细节

• 为什么要代替的是大于等于a[i]的值在单调栈的元素？这样存储的完全不是最长上升子序列了啊！

  我们此时无法用纯粹的单调栈的方法存储那个符合的序列
  如：3 1 2 3 2 8 5 6
  我们存储了 1 2 3 之后，如果再指到2，我们按以往单调栈的模板，应该栈清除到只有1，再把2入栈，此时显然结果会错误。
  此时应该做的是：找寻当前栈中大于等于这个元素的最小值并替代它，而如果大于队尾元素的值，就直接入栈。此时显然我们栈存储的就不是最大上升序列本身了，而维持着a[i]结尾的这个序列中，当前最大队列的长度。
  而查询这个值的位置，显然应该使用二分搜索

2.具体代码

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 100010, n;
    static int[] stk = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        String [] str = br.readLine().split(" ");
        int tt = 0;
        stk[0] = Integer.parseInt(str[0]);
        for (int i = 1; i < n; i++) {
            int x = Integer.parseInt(str[i]);
            if (x > stk[tt]) stk[++tt] = x;
            else{
                int l = 0, r = tt;
                while (l < r){
                    int mid = l + r >> 1;
                    if (stk[mid] < x) l = mid + 1;
                    else r = mid;
                }
                stk[l] = x;
            }
        }
        System.out.println(tt+1);
    }
}

python3

stk = []
n = int(input())
a = [int(x) for x in input().split()]

for i in range(n):
    if not stk or a[i] > stk[-1]:
        stk.append(a[i])
    else:
        # r代表下标故需要减1
        l, r = 0, len(stk) - 1
        while l < r:
            mid = l + r >> 1
            if stk[mid] < a[i]: l = mid + 1
            else:   r = mid 
        stk[l] = a[i]

print(len(stk))

C++

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n, a, stk[N], tt;

int main()
{
    cin >> n;
    cin >> a;
    stk[++tt] = a;

    for(int i = 0; i < n - 1; i ++)
    {
        cin >> a;
        if(a > stk[tt]) stk[++tt] = a;
        else
        {
            int l = 1, r = tt;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(stk[mid] < a) l = mid + 1;
                else    r = mid;
            }
            stk[l] = a;
        }
    }
    cout << tt;
    return 0;
}