#include <iostream>
#include <queue>
#include <stdlib.h>
#include <stdio.h>
#include <map>
#include <string>
#include <cstdlib>
#include <stack>
#include <vector>
#include <math.h>
#include <algorithm>
#include <typeinfo>
#include <cstring>

using namespace std;
int data[100],dp[100];
int main(int argc, char const *argv[])
{
    int n;
    while(cin>>n){
        memset(data,0,sizeof(data));
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++){
            cin>>data[i];
        }
                //转换成lis
        reverse(data,data+n);
        int pos=0;
        dp[0]=data[0];
        for(int i=1;i<n;i++){
            if(data[i]>=dp[pos]){
                dp[++pos]=data[i];
            }else{
                *upper_bound(dp,dp+pos+1,data[i])=data[i];
            }
        }
        cout<<pos+1<<endl;
    }
    return 0;
}

//最长降序序列，动态规划来做
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int k;
    while(scanf("%d",&k)!=EOF){
        vector<int> height(k,0);
        for(int i=0;i<k;i++){
            scanf("%d",&height[i]);
        }
        vector<int> dp(k,1);
        dp[0]=1;
		int maxVal=1;
        for(int i=1;i<k;i++){
            for(int j=i;j>0;j--){
                if(height[i]<=height[i-j]){
                    dp[i]=max(dp[i],dp[i-j]+1);
                }
            }
			if(maxVal<dp[i]){
				maxVal=dp[i];
			}
        }
        printf("%d\n",maxVal);
    }
}

//LIS最长递增子序列
//最长递增子序列是在给定序列中，不改变序列顺序的前提下找出最长的递增序列
//LIS[i]表示以LIS[i]结尾的最长递增子序列
//如果序列长度为1，那个最长序列长度为1，即LIS[0]=1
//如果i！=0，给出一个例子加以说明
//186 186 150 200 160 130 197 220
//如果要求i=6即以197结尾的最长子序列
//LIS[0]=1;LIS[1]=1;LIS[2]=1
//LIS[3]=2,因为200>150，即大于以150为结束位的最长子序列中的每一个值
//所以直接在150对应的LIS[2]的基础上加一
//LIS[4]=2，同理
//LIS[5]=1
//LIS[6]=3,197同时满足大于150,160，但是我们要求最长的子序列，所以选择LIS[2]LIS[4]中较大值

//所以确定LIS[i](i!=0)的方法是：遍历 a[0]~a[i-1] 找到比a[i]小的数
//在这些数对应的LIS值中找到最大值，加一即可
//如果没有找到比a[i]小的数，则LIS[i]=1 

//最后遍历LIS数组，找到最大值就是最长递增子序列的长度值 


#include<stdio.h>
int main(){
	int n,i,j;
	int a[30];
	int LIS[30]; 
	while(scanf("%d",&n)!=EOF){
		for(i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		LIS[0]=1;
		for(i=1;i<n;i++){
			int max=0;
			for(j=i-1;j>=0;j--){
				if(a[i]<=a[j]){
					if(LIS[j]>max)
						max=LIS[j];
				}
			}
			LIS[i]=max+1;
		}
		int max=0;
		for(i=0;i<n;i++){
			if(LIS[i]>=max){
				max=LIS[i];
			}
		}
		printf("%d\n",max);
	}
}

while True:
    try:
        num = int(input())
        digitsList = list(map(int,input().split()))
        dp = [1]*num
        for i in range(num):
            for j in range(i):
                if digitsList[i] <= digitsList[j]:
                    dp[i] = max(dp[i],1+dp[j])
        print(max(dp))
        print(dp)
    except Exception:
        break

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            int n = scan.nextInt();
            int[] F = new int[n];
            int[] arr = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = scan.nextInt();
            }
            F[0] = 1;
            for(int i=1;i<n;i++){
                F[i] = 1;
                int max = 1;
                for(int j=i-1;j>=0;j--){
                    if(arr[j]>=arr[i]){
                        if(max<F[j]+1)
                            max = F[j] + 1;
                    }
                }
                F[i] = max;
            }
            int max = 0;
            for(int i=0;i<n;i++){
                if(F[i]>max)
                    max = F[i];
            }
            System.out.println(max);
        }
    }
}

#include<stdio.h>

int main()
{
    int k,i,j,max;
    while(scanf("%d",&k)!=EOF)
    {
        int d[26]={0},num[26]={0,1};
        for(i=1;i<=k;i++)
            scanf("%d",&d[i]);
        max=1;                      /*max表示最多拦截的**数*/
        for(i=2;i<=k;i++)
        {
            num[i]=1;                /*以d[i]结尾的子列长度最短为1*/
            for(j=i-1;j>=0;j--)     /*从d[i-1]开始向前寻找值小于d[i]的数的d[k]，则num[i]=max{num[i],num[j]+1}*/
               if(d[j]>=d[i])
                    num[i]=(num[j]+1>num[i])?num[j]+1:num[i];   /*num[i]不能换成1，因为在向前循环时num[i]可能大于1*/
            max=max>num[i]?max:num[i];/*寻找最长子列*/
        }
        printf("%d\n",max);
    }
    return 0;
}

最大下降子序列（包含相等的）

#include <bits/stdc++.h>
using namespace std;
int main(){
	int k,a[30],maxsum[30];
	cin>>k;
	for(int i=0;i<k;i++) {
		cin>>a[i];
		maxsum[i]=1;
	}
	
	for(int i=0;i<k;i++)
		for(int j=0;j<i;j++){
			if(a[j]>=a[i]) maxsum[i]=max(maxsum[i],maxsum[j]+1);
		}
	cout<<*max_element(maxsum,maxsum+k);
	return 0;
}

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int k;
    while(cin>>k){
        vector<int> a(25);
        for(int i=0;i<k;i++){
            cin>>a[i];
        }
        vector<int> dp(k);
        dp[0] = 1;
        for(int i=1;i<k;i++){
            dp[i] = 1;
            for(int j=0;j<i;j++){
                if(a[i]<=a[j])  dp[i] = max(dp[i],dp[j] + 1);
            }
        }
        cout<<*max_element(dp.begin(),dp.end())<<endl;
    }
}

k=int(input())
h=list(map(int,input().split()))
dp=[0]*(k+1)
for i in range(1,k+1):
    dp[i]=1
    for j in range(1,i):
        if h[j-1]>=h[i-1]:dp[i]=max(dp[j]+1,dp[i])
print(max(dp))

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			
			int[] arr = new int[n];
			
			int[] dp = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = scanner.nextInt();
				dp[i] = 1;	//初始化dp[i]为1，最少拦截1枚
			}
			
			int answer = 0;
			for (int i = 0; i < dp.length; i++) {
				for (int j = 0; j < i; j++) {
					if(arr[j] >= arr[i]) {	//可以把i拼到以a[j]为结尾的递减子序列中
						dp[i] = Math.max(dp[i], dp[j] + 1);
					}
				}
				answer = Math.max(answer, dp[i]);
			}
			
			System.out.println(answer);
		}
	}
}

#include <cstdio>
#include <iostream> //max()
using namespace std;

int main(){
    int height[26]; //导弹高度
    int dp[26];     //能拦截的导弹数目
    int n;
    while(scanf("%d",&n) != EOF){
        for(int i = 0; i < n; ++i){
            scanf("%d",&height[i]);
        }
        int answer = 0;
        for(int i = 0; i < n; ++i){
            dp[i] = 1; //初始化为1，最少能拦截第一枚(若是递增就只能拦截一枚)
            for(int j = 0; j < i; ++j){
                if(height[j] >= height[i]){
                    dp[i] = max(dp[i],dp[j] + 1);
                }
            }
            answer = max(answer,dp[i]);
        }
        printf("%d\n",answer);
    }
    return 0;
}

#include <iostream>
using namespace std;
int main() {
    int n, i, j;
    cin >> n;
    int a[n], dp[n], max1 = 0;
    for (i = 0; i < n; i++) {
        dp[i] = 1;
        cin >> a[i];
        if (i != 0) {
            //找一个dp最大的，并且比当前值大的
            int index = -1, max2 = 0;
            for (j = i - 1; j >= 0; j--) {
                if (a[i] <= a[j] && dp[j] > max2) {
                    max2 = dp[j];
                    index = j;
                }
            }
            if (index == -1)
                dp[i] = 1;
            else
                dp[i] = dp[index] + 1;
        }
        max1 = max(max1, dp[i]);
    }
    cout << max1;
}

自顶向下递归

#include <climits>
#include <vector>
#include <iostream>
using namespace std;

// 导弹袭击
// 后一发不能高于前一发
int get(int height,vector<int> a,int index){
    if(index == a.size()-1){
        if(a[index]<=height) return 1;
        return 0;
    }
    int left,right;
    right = get(height,a,index+1);
    if(a[index] <= height){
        left = 1 + get(a[index],a,index+1);
        
    }else{
        left = right;
    }
    return max(left,right);

}

int main() {
    int a;
    while(cin >> a){
        vector<int> arr(a);
        for(int i=0; i < a;++i){
            cin >> arr[i];
        }
        cout << get(INT_MAX,arr,0) << endl;

    }
}
// 64 位输出请用 printf("%lld")