#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int a[N],dp[N],nmax;
int main(){
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	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);
			}
		}
		nmax = max(nmax,dp[i]);
	}
	cout << nmax;
	return 0;
}

LIS模板题

这道题是LIS的模板题，因为他在LIS的训练里

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int n,a[1001],dp[1001],maxn=1;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i]=1;//设置边界
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(a[j]<a[i])//判断是否上升
			{
				dp[i]=max(dp[i],dp[j]+1);//状转
			}
		}
		maxn=max(dp[i],maxn);//比较最大值
	}
	cout<<maxn;
}

`#include<bits/stdc++.h> using namespace std; const int N=1e5+10; const int INF=0x3f3f3f3f; int n,a[N],dp[N],maxx; int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; dp[i]=1; } 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); } } maxx=max(maxx,dp[i]); } cout<<maxx;

return 0;

} `

#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n,a[N],dp[N],maxx,a;
int main()
{
	cin>>n>>a;
	for(int i=1;i<=n;i++)
	{ 
		cin>>a[i];
		dp[i]=1;}
	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);
			}
		}
		maxx=max(maxx,dp[i]);
	}
	cout<<maxx;
	return 0;//1348
}

1

#include<bits/stdc++.h>
using namespace std;
int n;
int maxv=-114514;
int A[110000];
int dp[110000];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>A[i];
	}
	for(int i=1;i<=n;i++){
		dp[i]=max(dp[i-1]+A[i],A[i]);
		maxv=max(maxv,dp[i]); 
	}
	cout<<maxv;
}

// 7
// 1 7 3 5 9 4 8

// 1 7 9 

// 1 3 5 8
// 1 3 5 9
/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int a[N] , n ,dp[N];
int main()
{
	cin >> n;

	for(int i = 0 ; i< n ; i++)
		cin >> a[i];
	
	int maxx =0;
	for(int i = 0 ; i < n ; i++)
	{
		dp[i] = 1;
		for(int j = 0 ; j < i ; j++)
		{
			if(a[i] > a[j])
			{
				dp[i] = max(dp[i] , dp[j]+1);
			}
		}
		maxx = max(dp[i] ,maxx);
	}
	cout << maxx <<endl;
	return 0;
}