Skip to content

二分查找#

目录#

1. 模板#

DP方法，复杂度为 

#include<iostream>
using namespace std;

const int NUM  = 5e4 + 1;
long long n, list[NUM];

// 求最长上升子序列长度
int LIS()
{
    int ans = 1;
    int dp[MAXN];
    dp[1] = 1;
    // 对所有数进行循环
    for (int i = 0; i <= n; i++) {
        int max = 0;
        // 对所有小于i的数进行循环
        for (int j = 1; j < i; j++) {
            // 若找到符合条件的最大值
            if (dp[j] > max && list[j] < list[i]) {
                // 记录最大值
                max = dp[j];
            }
        }
        // 将当前遍历的数位计算在内，当前的最长上升子序列长度为max + 1
        dp[i] = max + 1;
        if (dp[i] > ans) {
            ans = dp[i];
        }
    }
    return ans;
}

非DP方法，复杂度为 

#include<iostream>
using namespace std;

const int NUM  = 5e4 + 1;
long long n, list[NUM];

int LIS()
{
    long long len = 1;
    long long d[NUM];
    // 初始化
    d[1] = list[1];
    // O(n)
    for (int i = 2; i <= n; i++) {
        // 符合递增的要求，加入
        if (list[i] > d[len]) {
            d[++len] = list[i];
        } else {
            // 替换，O(logn)
            long long j = lower_bound(d + 1, d + len + 1, list[i]) - d;
            d[j] = list[i];
        }
    }
    return len;
}
Back to top