动态规划-单调递增最长子序列（三）

题目如下：

求一个字符串的最长递增子序列的长度如：dabdbf最长递增子序列就是abdf，长度为4；

找出共同子问题：

推理：

比如我们有序列bdbf，那么我们在选定了b（第一个）之后，那么它的最大长度就确定了那就是3，如果我们选择了d,那么它的长度就为2（不考虑前边的b这个元素）；依次类推，选择第二个b为2，选择f为1；

假如在该字符串前添加元素a，它并不会影响到后边的元素的所对应的最大长度；那么我们可以很容易的算出a的最大长度为多少？

怎么算的呢？在选定a的情况下选定b（第一个），显然有dis[b] +1 = 4,如果不选定b而选择d呢？显然有dis[d]+1 = 3(小于原先的值去除)依次类推，可以得到最大值为4；

可能有人会纳闷了？显然a

对于gbdf，对应的值为1,3,2,1；如果往前添加a的话，难道判断a

针对上方的序列，不妨画图解释下整个流程：

f

1

b f

2 1

d b f

2 2 1

b d b f

3 2 2 1

a b d b f

4 3 2 2 1

d a b d b f

3 4 3 2 2 1

接下来开始写代码吧，很容易就写出来的：

import java.util.Arrays;
//单调递增最长子序列
public class LongestSubSeq {
	private int[] dis;
	private String str;
	
	public LongestSubSeq(String str){
		this.str = str;
		dis = new int[str.length()];
		Arrays.fill(dis, 1);
	}
	
	private int getLongestCount() {
		// TODO Auto-generated method stub
		char[] c = str.toCharArray(); 
		
		for(int i = dis.length-2;i>=0;i--){
			for(int j = i;j < dis.length;j++){	
				if(c[i] <= c[j]){
					dis[i] = Math.max(dis[i],dis[j]+1);
				}
			}
		}
		
		int max =0;
		for(int i = 0;i