Comment

SoulPowering...: 2026-04-16 16:39:50

法二：贪心+二分法，O(nlogn)!!!,极大地优化，比dp方法快几百倍！！



//最长上升子序列2
//更快O(nlogn),贪心
//不用像dp一样枚举后接在所有的数后面
//直接直接到最长子序列的最小结尾值处

//“结尾越小越好”，因为越小越容易接后面的数。
// 为什么只维护“最小结尾”就够了

// 比如长度都是 3：

// 一个长度 3 的上升子序列结尾是 10
// 另一个长度 3 的上升子序列结尾是 7

// 那显然结尾 7 更优。

// 因为以后来了一个新数 8：

// 7 可以接 8
// 10 不能接 8

// 所以同样长度下，我们只保留“结尾最小”的那个状态。

// 这就是贪心的核心。

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@2

//推广到最长非降子序列2
//更快O(nlogn),贪心
//和上升的区别：上升必须接在>后面，但非降可以接在>=后面
//同样，当前长度为i的子序列结尾值越短越好，q[i]仍然记录最小结尾值

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int a[N];
int q[N];
//q[len],长度为len的上升子序列的最小结尾值；
//严格单增
int main()
{
    int m;
    cin>>m;
    while(m--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        
        int len=0;//当前的lIS最大长度

        //每一组数据都要重新初始化！
        q[0]=-2e9;
        for(int i=1;i<=n;i++)q[i]=0;

        for(int i=1;i<=n;i++)//枚举a[i]
        {
            //在q[0~len]中二分查找最大的<a[i]的q[j],表示长度为j的上升子序列还能在接一个
            //len+1,q[len+1]=a[i]
            
            //为了保证每次二分都能找到一个满足的，设置哨兵q[0]=-2e9;
            int l=0,r=len;

            //若为非降，查找性质变为小于等于<=,不行，这样就变成死循环了，嗯……
            //while(l<=r)嘿嘿嘿乱搞了哈，二分终止条件永远是l==r，改二分查找的性质是在if()判断里面！！
            while(l<r)
            {
                int mid =l+r+1>>1;
                if(q[mid]<=a[i])l=mid;
                else r=mid-1;
            }

            len=max(len,r+1);//可能变更大(搜到了最后一个数，延长)，可能不变
            q[r+1]=a[i];
        }
        cout<<len<<endl;
    }
    return 0;
}

SoulPowering...: 2026-04-16 16:38:48

法一：线性dp，O（n^2）,比较朴素

#include<iostream>
#include<algorithm>
using namespace std;

//注意常数根据具体题目确定！！
const int N=10010,INF=1e9;
//注意如果是字母，-1e9存入char可能就不是负无穷了。
//注意数据类型
int a[N];
int f[N];
//f[i]:以a[i]结尾的最大上升子序列长度
    //集合：以a[i]结尾的所有上升子序列
    //属性：max
int main()
{
    //O(n^2)
    int m;
    //记得加上&
    scanf("%d",&m);
    while(m--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        
        int res=0;
        for(int i=1;i<=n;i++)
        {
            f[i]=1;
            for(int j=1;j<=i-1;j++)
                if(a[i]>=a[j])f[i]=max(f[i],f[j]+1);    
            res=max(res,f[i]);
        }
        printf("%d\n",res);
    }
    return 0;
}

Huhu_Miao: 2025-05-18 21:05:39

/**
 *    author:  Huhu_Miao
 *    created: 2025.5.18 21:04:56 (UTC+8)
**/
#include<iostream>
#include<algorithm>

constexpr int N = 10001;
int arr[N], dp[N];
void solve(){
	int n; std::cin >> n; 
	for(int i = 0 ; i < n ; i++) std::cin >> arr[i];
	for(int i = 0 ; i < n ; i++){
		dp[i] = 1;
		for(int j = i - 1 ; j >=0 ;j--)
			if(arr[j] <= arr[i]) dp[i] = std::max(dp[j] + 1 , dp[i]);
	}
	int * ptr = std::max_element(dp,dp+n);
	std::cout << *ptr << '\n';
}

int main(){
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
	int T; std::cin>>T;
	while(T--) solve();
	return 0;
}

71123140焦博宇: 2025-05-15 11:40:37

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<climits>
#include<iomanip>
using namespace std;

int x[10005], dp[10005];

int main()
{
	int M;
	cin >> M;
	for (int i = 1; i <= M; i++)
	{
		int N;
		cin >> N;
		int Max = INT_MIN;
		for (int i = 1; i <= N; i++)
			cin >> x[i];
		for (int i = 1; i <= N; i++)
			dp[i] = 1;
		for (int i = 2; i <= N; i++)
		{
			for (int j = 1; j <= i - 1; j++)
			{
				if (x[j] <= x[i])
					dp[i] = max(dp[j] + 1, dp[i]);
			}
			Max = max(Max, dp[i]);
		}
		cout << Max << endl;
	}
	return 0;
}

Westbrook: 2024-05-11 10:58:24

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int f[N];
int m;

int main()
{
	cin >> m;
	while (m--)
	{
		memset(a, 0, sizeof a);
		memset(f, 0, sizeof f);
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];

		for (int i = 1; i <= n; i++)
		{
			f[i] = 1;
			for (int j = 1; j < i; j++)
			{
				if (a[j] <= a[i])
				{
					f[i] = max(f[i], f[j] + 1);
				}
			}
		}
		int res = 0;
		for (int i = 1; i <= n; i++)
		{
			res = max(res, f[i]);
		}
		cout << res << endl;
	}
	return 0;
}样例不需要优化，需要注意初始化以及相等也加进去的情况

Westbrook: 2024-04-26 10:45:23

#include<iostream>
#include<cstring>
using namespace std;
const int N = 10010;
int f[N];
int a[N];
int m, n;

int main()
{
	cin >> m;
	while (m--)
	{
		cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        int cnt = 0;
        f[cnt++] = a[0];
        for (int i = 1; i < n; i++) {
            if (a[i] > f[cnt - 1]) f[cnt++] = a[i];
            else {
                int l = 0, r = cnt - 1;
                while (l < r) {
                    int mid = (l + r) >> 1;
                    if (f[mid] >= a[i]) r = mid;
                    else l = mid + 1;
                }
                f[r] = a[i];
            }
        }
        cout << cnt << endl;

	}
	return 0;
}//
实在不理解哪错了