// write your code here cpp
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n;
    while(cin >> n){
        vector<int> height(n, 0);
        for(int i = 0; i < n; i ++){
            cin >> height[i];
        }
        
        vector<int> f(n, 1);
        int result = 1;
        for(int i = 1; i < n; i ++){
            for(int j = 0; j < i; j ++){
                if(height[i] > height[j]){
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            result = max(result, f[i]);
        }
        
        cout << result << endl;
    }
}

烂大街的题目。python解法，时间复杂度nlogN

import bisect

while True:
    try:
        a, b = input(), map(int, input().split())
        q = []
        for i in b:
            pos = bisect.bisect_left(q, i)
            if pos == len(q):
                q.append(i)
            else:
                q[pos] = i
        print(len(q))
    except:
        break

// write your code here
import java.util.Scanner;

public class Main {
	
	
	public static int findLongest2(int[] A, int n){
		int[] dp = new int[n];
		dp[0] = 1;
		
		int[] ends = new int[n];
		
		ends[0] = A[0];
		//右哨兵
		int right = 1;
		
		int maxLength = dp[0];
		for(int i = 1;i<n;i++){
			//二分查找第一个比自己大的数，替代之，如果没找到，写在后边
			int start = 0;
			int end = right-1;
			int resultPos = right;
			while(start <= end ){
				int mid = start + (end - start)/2;   //重要
				if(ends[mid]>=A[i]){
					resultPos = mid;
					end = mid - 1;
				}else
					start = mid + 1;
			}
			ends[resultPos] = A[i];
			if(resultPos == right)
				right++;
			dp[i] = resultPos + 1;
			maxLength = Math.max(maxLength, dp[i]);
		}
		return maxLength;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();
			int[] data = new int[n];
			for(int i = 0;i<n;i++){
				data[i] = sc.nextInt();
			}
			System.out.println(findLongest2(data, n));
		}
	}
}

import java.util.Scanner;

/**
 * Created by Olive on 2017/9/7.
 * ***上站着一支队伍，她们是来自全国各地的扭秧歌代表队，现在有她们的身高数据，
 * 请你帮忙找出身高依次递增的子序列。 例如队伍的身高数据是（1、7、3、5、9、4、8），
 * 其中依次递增的子序列有（1、7），（1、3、5、9），（1、3、4、8）等，其中最长的长度为4。
 */
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int[] height = new int[n];
            for(int i = 0; i < n; i++){
                height[i] = in.nextInt();
            }
            System.out.println(longest(height, n));
        }
    }

    public static int longest(int[] height, int n){
        if(height == null || n <= 0 || height.length != n)
            return 0;
        // dp[i]代表以i为结尾的最长递增子序列的长度
        int[] dp = new int[n];
        dp[0] = 1;
        int max = 1;
        for(int i = 1; i < n; i++){
            dp[i] = 1;
            for(int j = i - 1; j >= 0; j--){
                if(height[i] > height[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            if(max < dp[i])
                max = dp[i];
        }

        return max;
    }
}

#include <iostream>
using namespace std;
int main(){
    int N;
    while(cin >> N){
        int  a[10002], dp[10002] = {0}, m=0;
	for (int i = 1; i <= N; i++) cin >> a[i];
	for (int i = 1; i <= N; i++)
		for (int j = 1; j < i; j++)
			if (a[j] < a[i])
				dp[i] = max(dp[i], dp[j] + 1), m = dp[i] > m ? dp[i] : m;
	cout << m + 1 << endl;
    }
    return 0;
}

try:
    while True:
        num,digitsList = int(input()),list(map(int,input().split()))
        subSeries = []
        maxLen = 0
        subSeries.append(digitsList[0])  #辅助数组
        for i in range(1,num):
            if digitsList[i] > subSeries[maxLen]:
                maxLen += 1
                subSeries.append(digitsList[i])
            else:
                left,right = 0,maxLen
                while left <= right:    #在已有的subSeries数组范围内二分查找到比该数大的最小数替换掉
                    mid = (left+right)//2
                    if digitsList[i] > subSeries[mid]:
                        left = mid+1
                    else:
                        right = mid-1
                subSeries[left] = digitsList[i]
    #        print(" ".join(map("{:>2}".format, subSeries)))  #每次打印出来观察
        print(maxLen+1)
except Exception:
    pass

import java.util.Scanner;
public class Main{
 	   public static void main(String[] args){
	        Scanner cin=new Scanner(System.in);
	        while(cin.hasNext()){
	            int number=cin.nextInt();
				int result=1;//结果
	            int[] arr=new int[number];//数据初始化
	            for(int i=0;i<number;i++){
	                arr[i]=cin.nextInt();
	            }
	            int[] dp=new int[number];
	            dp[0]=1;
	            for(int i=0;i<number;i++){
	                dp[i]=1;
	                for(int j=0;j<i;j++){
	                    if(arr[j]<arr[i]&&dp[j]>=dp[i]){
                            dp[i]=dp[j]+1;
                            result=dp[i]>result?dp[i]:result;
                        }
	                }
	            }
	            System.out.println(result);
	            
	        }
	    }
	}

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

#define INF 1000000
using namespace std;

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	int n;
	while (cin >> n && n > 0)
	{
		vector<int> height(n), dp(n, 1);
		int maxLen = 1;
		for (int i = 0; i < n; ++i)
		{
			cin >> height[i];
			for (int j = i - 1; j >= 0; --j)
				if (height[j] < height[i]) dp[i] = max(dp[i], dp[j] + 1);
			maxLen = max(maxLen, dp[i]);
		}
		cout << maxLen << endl;
	}

	return 0;
}

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			int[] m = new int[n];
			for (int i = 0; i < n; i++) {
				m[i] = sc.nextInt();
			}
			int[] dp = new int[n];
			dp[0] = 0;
			int max = 0;
			for (int i = 1; i < n; i++) {
				for (int j = 0; j < i; j++) {
					if (m[j] < m[i]) {
						dp[i] = Math.max(dp[j] + 1, dp[i]);
						if (max < dp[i]) {
							max = dp[i];
						}
					}
				}
			}
			System.out.println(max + 1);
		}
	}
}

#include <cstring> 
#include <cstdio>
#include <cstdlib> 
#include <algorithm>
#define MAX 1000+5
using namespace std;

int n;
int dp[MAX];//dp[i]表示长度为i+1的最长上升子序列的末尾元素最小值
int m[MAX];
int LIS(int* m){
	int len=0;
	dp[len]=m[0];
	for(int i=1;i<n;++i){
		if(dp[len]<m[i]){
			dp[++len]=m[i];
		}
		else{
			*lower_bound(dp,dp+len,m[i])=m[i];//二分查找
		}
	}
	return len+1;
}
int main()
{
	while(scanf("%d",&n)!=EOF){
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;++i)
			scanf("%d",&m[i]);
		if(m){
			printf("%d\n",LIS(m));
		}
	}
	return 0;
}

// write your code here cpp
#include<iostream>
#include<vector>
using namespace std;
int getHeight2(vector<int> men, int n)
{ //法二: help数组加速   时间复杂度O(nlogn)
 int* help=new int[n];
 int left=0,right,mid,r=0;
 if(n==0) return 0;
 help[0]=men[0];
 for(int i=1;i<n;i++)
 {
  if(men[i]>help[r]){r++;help[r]=men[i];}
  else{
    left=0;
          right=r;
    while(left<=right)
    {
     mid=(left+right)/2;
     if(men[i]>help[mid])left=mid+1;
     else right=mid-1;
    }
    help[left]=men[i];
  }
 }
 delete[] help;
    return r+1;
}
 
int main()
{
 int n;
    while(cin>>n){
 int* b=new int[n];
 for(int i=0;i<n;i++)
  cin>>b[i];
    vector<int> a(b,b+n);
    cout<<getHeight2(a,a.size())<<endl;
 delete []b;
 }
 return 0;
}
思路：构造一个辅助数组help，help数组维持了一个递增序列，依次遍历原始数组，如果大于help数组的最后一个数（最大的数），将其加入help数组末尾，help数组长度增长，else 用二分法找到第一个比当前元素大的数，并用当前元素替换该数。这样遍历结束，help维持的递增序列长度就是所求的数。

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

int main()
{
	int n;
	while (cin >> n)
	{
		vector<int> data(n);
		vector<int> state(n);
		for (int i = 0; i<n; i++)
		{
			cin >> data[i];
			int maxlength = 0;
			for (int j = 0; j<i; j++)
			{
				if (data[j]<data[i])
				{
					if (state[j]>maxlength)
						maxlength = state[j];
				}
			}
			state[i] = maxlength + 1;
		}
		int result = 0;
		for (int i = 0; i<n; i++)
			result = result>state[i] ? result : state[i];
		cout << result << endl;
	}
}

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


int LIC(vector<int> &v,int n)
{
    vector<int> dp(n,1);
    int res=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(v[i]>v[j])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        res=max(res,dp[i]);
    }
    return res;
}

int main() {
    int n;
    int result;
    while (cin >> n)
    {
        vector<int> v(n);
        for(int i=0;i<n;i++)
        {
            cin>>v[i];
        }
        cout<<LIC(v,n)<<endl;
    }
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            
        
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] res = new int[n];
        for(int i = 0;i < n;i++){
            arr[i] = sc.nextInt();
            //res数组里面的元素都初始化为1
            res[i] = 1;
        }
        
        for(int i = 1;i < arr.length;i++){
            for(int j = 0;j < i;j++){
                //遍历i之前的数，如果i位置的元素大，就动态规划进行比较
                if(arr[i] > arr[j]){
                    res[i] = Math.max(res[i],1 + res[j]);
                }
            }
        }
        
        //最后返回res里面存储的最长子序列的值
        int t = Integer.MIN_VALUE;
        for(int i = 0;i < res.length;i++){
            if(t < res[i]){
                t = res[i];
            }
        }
        System.out.println(t);
        }
    }
}