题目：
给定一个 $n$ 个数组成的数据，设计算法找出其中最长单调递增子序列，要求算法复杂度不超过$O(n^2)$。

一、问题分析（模型、算法设计和正确性证明等）

​ 假设已经求出前n个数据的递增长度子序列的长度了。求n+1的时候，n+1项的数据直接和前n项的数据挨个比较，然后找出前n的递增长度子序列长度最大的加1就行了。求递增子序列就是该过程的逆过程。找出递增最大的项M数据，然后减一，找前面的数据比M数据小，而且长度比其小一的数据就是成员之一。依次查找就可以找到最长递增能子序列。

二、复杂度分析

伪代码：

//求最大单调递增子序列的长度
public class DP_riseSbuseq{
    int ins[n];	//长度为n的原始序列
    int dp[n]; 	//用于存放以各个元素结尾的序列的最大长度
    for(int i=0;i<nli++){
        dp[i]=1;//每次先将以ins[i]结尾的最大增序列长度dp[i]初始化为1
        for(int j=0;j<i;j++){
            if(ins[j] < ins[i]){
                if(dp[j]+1 > dp[i]){
                    dp[i] = dp[j]+1;
                }
           	}
        }
        if(dp[i] > result) result = dp[i]; //result即为最大长度
    }
    return result;
}
//求出该子序列
public class DP_getSeq{
    int length = result,index=0;//将上面的result赋给length，在dp[]中查找其下标index
    for(int i=0;i<dp.length;i++){
        if(dp[i]==length) index =i; //查找最长子序列的最后一个元素下标
    }
    //逆向查找组成子序列的元素
    int seq[];//用于存在子序列
    seq[--length]=ins[index];
    for(int i=index;i>=0;i--){
        if(ins[i] < ins[index] && dp[i] == dp[index]-1){
            seq[--length] = ins[i];	
            index = i;	//满足条件则赋值，并且将index向前移动。
        }
    }
    return seq;
}

​ 伪代码分为两部分，分别是求最大长度和求子序列，容易发现求最大长度时用了一个嵌套的循环，求子序列只用了一个循环。所以时间复杂度为$O(n^2)$ 符合题目不超过$O(n^2)$的要求。

三、代码(java)

package root;

import java.util.Scanner;

/**
 * @author 宇智波Akali
 * 求最长单调递增子序列（不是子串）
 */
public class T4_DP_riseSubSeq {
	public static void main(String[] args) {
		//数据输入
		Scanner input = new Scanner(System.in);
		System.out.println("请输入原始序列：");
		String str = input.nextLine();
		String strs[] = str.split(" ");
		int ins[] = new int[strs.length];
		input.close();
		for(int i=0; i<strs.length;i++){
			ins[i] = Integer.parseInt(strs[i]);
		}
		//得到一组序列ins[]
		int dp[] = new int[ins.length];
		int result=0;
		for(int i=0; i<ins.length;i++){
			dp[i] = 1;//每次先将以ins[i]结尾的最大增序列长度dp[i]初始化为1
			for(int j=0;j<i;j++){
				if(ins[j] < ins[i]){
					if(dp[j]+1 > dp[i]){
						dp[i] = dp[j]+1;
					}
				}
			}
			if(dp[i] > result){
				result = dp[i];
			}
		}
		
		int length = result,index=0;	//length就是所求子序列的长度
		//	找到dp[i]中的最大值和对应的下标index
		for(int i=0;i<dp.length;i++){
			if(dp[i] == length){
				index = i;
			}
		}
		int seq[] = new int[result];	//创建数组用于保存最长增子序列
		seq[--length] = ins[index];	//先找到最大值，也就是最大增子序列的最后一个
		for(int i=index;i>=0;i--){	//逆序寻找子结构，然后构成所求子序列
			if(ins[i] < ins[index] && dp[i] == dp[index]-1){	//i从最大增子序列的最后一个元素的下标index开始，反向查找
				seq[--length] = ins[i];							//满足前一项小于后一项，并且前一项的dp[]等于后一项的dp[]+1（这两个条件就是上面寻找最大个数的判断条件）
				index = i;										//满足条件则赋值，并且将index向前移动。
			}
		}
		
		
		System.out.print("最长单调递增子序列为：");
		for(int i=0;i<result;i++){
			System.out.print(seq[i]+" ");
		}
		System.out.println("\n最长单调递增子序列长度为：" + result);
	}


}

只是找到最大子序列长度倒是还好，要将该序列输出就还需要逆向查找组成子序列的子结构。

以下为测试结果：

最长单调连续递增子序列：
一开始没仔细读题目，把求子序列求成了子串，也就是最大连续增子序列，这和题目是两个问题，但是也很有趣。既然做了，也把代码放上吧，时间复杂度仅为$O(n)$。

public calss continue_rSeq{//	最大连续增子序列
    int ins[];//为原始序列
    int num = 1;//num是已有的增序列长度，因为循环从第二个元素开始，所以初始化单调增序列长度为1
    int t1 = 0,t2=0;// 定义两个锚点（锚点1是单点增序列的头部，锚点2是尾部）
    for(int i=1;i<ins.length;i++){
        if(ins[i] > ins[i-1]){	//当出现递增时(后一项大于前一项)
            if(t1 > t2){	//当锚点1在锚点2后面时(也就是出现了第二个递增序列时)
                if(i-t1+1 > num){	//判断当前活动锚点i与锚点1之间的序列长度，是否大于已有增序列长度num
                    num = i-t1+1; 	//如果第二个增序列长度大于第一个增序列，则重新给num赋值
                    t2 = i;			//并将锚点2移动到i处（移动锚点2意味着t2>t1,即更新了已有最长增序列为t1~t2）
                }
            }else{			//当锚点1在锚点2前面时，说明当前仅存在一个单调增序列，继续增加元素即可
                num += 1;
                t2 = i;		//锚点2后移
            }
        }else{//当后一项小于前一项，说明不是单调增，那么把锚点1跟着i后移，调整增序列的头部
            t1 = i;
        }
    }
    //经过一轮循环后，就可以得到最长单调增序列的长度num，尾部t2，在经过一个循环就可以将其提取出来
    return ins[t2-num+1:t2];
}