题意

给定数组,求其最长严格单调递增子序列的长度

限制: 数组长度不大于200

方法

计数

我们,用一个数组来记录到当前位置的最大长度.

那么更新一个位置时,就是在他之前的所有值小于它的长度中找最长的

以样例数据2 5 1 5 4 5为例,

初始化,所有最大长度为1

这样,我们再在所有最大长度中,找最大值即可

代码

#include<bits/stdc++.h>
using namespace std;
int a[210];
int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i =0;i<n;i++){
            scanf("%d",a+i);
        }
        vector<int>cnt(n,1); // 默认长度最大为1
        int ans = 1;
        for(int i =1;i<n;i++){
            for(int j = 0;j<i;j++){
                if(a[i] > a[j]){ // 柱子i更高
                    if(cnt[i] < cnt[j]+1){ // 更多的步数
                        cnt[i] = cnt[j]+1; // 更新长度
                    }
                }
            }
            ans = max(ans,cnt[i]); // 所有长度的最大值
        }
        printf("%d\n",ans);
    }
    return 0;
}

复杂度分析

时间复杂度: 对于每个位置,我们需要遍历从开始到它,所以总时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 主要消耗在 数组读入和记录每个位置的最大长度,所以空间复杂度为$O(n)O(n)$

二分查找

如果我们有一个数组,其下标表示长度,对应了达到这个长度的最后一个值的最小值.

那么当我们首次遍历数组时,想让当前的值value 对应的长度尽量长,那么需要尽可能在长度更长的中,寻找小于它的.

因此,如果上述的统计数组len2v满足单调性,那么其找到的位置i必定,长度更小的值更小,而长度更大的值更大,

即是 len2v[i-1] < value <= len2v[i] < len2v[i+1], 所以当用value 去更新 len2v[i]后, 依然保持其单调性

对一个单调性的数组,可以采取二分搜索

代码

#include<bits/stdc++.h>
using namespace std;
int a[210];
int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i =0;i<n;i++){
            scanf("%d",a+i);
        }
        vector<int>len2v(210,0x3f3f); // 记录 长度 和 达到这个长度的最后一个值的最小值
        int ans = 1;
        for(int i = 0;i < n;i++){
            int l = lower_bound(len2v.begin(),len2v.end(),a[i])- len2v.begin(); // 二分搜索 找到 这个值的放置位置
            len2v[l] = a[i]; // 更新 记录
            ans = max(ans,l+1); // 更新答案
        }
        printf("%d\n",ans);
    }
    return 0;
}

复杂度分析

时间复杂度: 在每次找位置的时候,是log级别的复杂度,所以总时间复杂度为$O(nlog(n))O(n\; log(n))$

空间复杂度: 主要消耗在 数组读入和记录长度 对应的 最小值,所以空间复杂度为$O(n)O(n)$