動態規劃-單調遞增最長子序列（三）

題目如下：

求一個字符串的最長遞增子序列的長度如：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