学步园

单调递增子序列(二)

描述

给定一整型数列{a₁,a₂...,a_n}（0

如：1 9 10 5
11 2 13的最长单调递增子序列是1 9 10 11 13，长度为5。

输入

有多组测试数据（<=7）
每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的下一行里有n个整数，表示数列中的所有元素.每个整形数中间用空格间隔开（0

数据以EOF结束 。
输入数据保证合法（全为int型整数）！

输出

对于每组测试数据输出整形数列的最长递增子序列的长度，每个输出占一行。

样例输入

7
1 9 10 5 11 2 13
2
2 -1

样例输出

5
1

来源

[521521]改编

上传者

ACM_赵铭浩

这里面对庞大的数据量 我们肯定采用直接的方法，这里有2种策略，
1 空间换时间，但是10W的数据 存完消耗太大
2动态规划   优化逻辑处理缩短时间。

这里明显选动态规划，那么我们就要确定问题中的子问题模型
首先对数字串想要改变最大递增子序列 那么加进来的数必须满足大于 原数字串中 最长递增子序列的末端值的最小值

那么问题确定下来了，我们需要处理的相关数据，我们要保存每次添加数字后的最长递增子序列的最小值

Dp[K]   表示 长度为k的增长子序列的末端值

最后Dp 的长度就是最长增长子序列的长度

每次加进来的数  只会增加Dp长度  或者修改一个值

证明如下
1Dp[i] 中不存在重复值
2Dp[i]单调增
3数据如果在Dp 中  那么他不会影响Dp的数据，他组成的子序列的最长就是他在Dp中的位置

4如果他不在Dp中  那么如果他大于Dp最大值 那么会使dp增长一位

                             如果小于Dp的最大值  那么他将只影响 比他大的最小的那个的Dp值

import java.util.Scanner;

public class Main {

    public
static void main(String[] args) {
       
Main growingSubsequence = new Main();
       
growingSubsequence.solution();
    }
    int[] Dp;
//Dp[i] 存放着 数据中长度为i的单调递增字符串的最小值
    int maxlen;
//存放数组的最大值
    Scanner
in;
    private void
insertdate(int date){
  
   
 int left = 1;
  
   
 int right = maxlen;
  
   
 int mid  = (left+right)
>>1;
  
   
 while(right > left){
  
   
   
 if(Dp[mid] > date){
  
   
   
   
 right = mid -1;
  
   
   
 }else if(Dp[mid] == date){
  
   
   
    
return;
  
   
   
 }else{
  
   
   
   
 left = mid +1;
  
   
   
 }
  
   
   
 
  
   
   
 mid = (left + right)>>1;
  
   
 }
  
   
 //最后可以保证 left右都会比date大
  
   
 //left左都别date小;  
 
  
   
 //left <= right
  
   
 
  
   
 if(maxlen == 0){