1 package dp;
2
3 /**
4 * 最长上升子序列问题
5 */
6 public class LongestIncreasingSubsequence
7 {
8 /**
9 * 原始dp
10 * @param arr
11 * @return
12 */
13 public static int maxLength(int[] arr)
14 {
15 int[] len = new int[arr.length] ; //以i为结尾的最长上升子序列
16 int[] mark = new int[arr.length] ;//标记以i为结尾的最长上升子序列的上一个节点所在的上上子序列位置
17 len[0] = 1 ;
18 mark[0] = -1 ;
19
20 int maxPos = 0 ;
21 for(int i=1 ; i<len.length ; i++)
22 {
23 len[i] = 1 ;
24 mark[i] = -1 ;
25 for(int j=i-1 ; j>=0 ; j--)
26 {
27 if(arr[j] < arr[i] && (len[j]+1) > len[i])
28 {
29 len[i] = len[j]+1 ;
30 mark[i] = j ;
31 }
32
33 }
34 if(len[maxPos] < len[i])
35 maxPos = i ;
36 }
37
38
39 int maxP = maxPos ;
40 while (maxP != -1)
41 {
42 System.out.println(arr[maxP]);
43 maxP = mark[maxP] ;
44 }
45 return len[maxPos] ;
46 }
47
48 /**
49 * 使用二分加速的dp
50 * @param arr
51 * @return
52 */
53 public static int maxLength2(int[] arr)
54 {
55 int[] len = new int[arr.length] ; //以i为结尾的最长上升子序列
56 int[] mark = new int[arr.length] ;//标记以i为结尾的最长上升子序列的上一个节点所在的上上子序列位置
57 int[] m = new int[arr.length+1] ;//标记长度为x的子序列的最小值在arr中的位置
58
59 int mLength = 1 ;
60 len[0] = 1 ;
61 mark[0] = -1 ;
62 m[1] = 0 ;
63
64 int maxPos = 0 ;
65 for(int i=1 ; i<len.length ; i++)
66 {
67 len[i] = 1 ;
68 mark[i] = -1 ;
69
70 int pos = binarySearch(arr , m , mLength , arr[i]) ;
71
72 if(pos != -1)
73 {
74 len[i] = len[pos]+1 ;
75 mark[i] = pos ;
76 }
77
78 if(mLength < len[i])
79 {
80 m[len[i]] = i ;
81 mLength++ ;
82 }
83 else if(arr[m[len[i]]] > arr[i])
84 {
85 m[len[i]] = i ;
86 }
87
88 if(len[maxPos] < len[i])
89 maxPos = i ;
90 }
91
92
93 int maxP = maxPos ;
94 while (maxP != -1)
95 {
96 System.out.println(arr[maxP]);
97 maxP = mark[maxP] ;
98 }
99 return len[maxPos] ;
100 }
101
102 /**
103 * 寻找arr中比k小的最大数
104 * @param n 表示m的长度
105 * @param m 表示标记长度为x的子序列的最小值的位置的数组
106 * @return 该元素在arr中的位置(为标记函数而服务的)
107 */
108 private static int binarySearch(int[] arr , int[] m , int n , int k) {
109 int lo = 1;
110 int hi = n;
111
112 while ((hi-lo) > 1)
113 {
114 int mid = lo + (hi-lo)/2 ;
115
116 if(arr[m[mid]] < k)
117 lo = mid ;
118 else
119 hi = mid ;
120 }
121
122 if(arr[m[hi]] < k)
123 return m[hi] ;
124 else if(arr[m[lo]] < k)
125 return m[lo] ;
126 else
127 return -1 ;
128 }
129
130 public static void main(String[] args) {
131 int[] arr = new int[]{
132 // 1,4,8,3,4,5
133 // 3,5,1,7,5,9,3,5
134 1, 7, 3, 5, 9, 4, 1
135 } ;
136
137 System.out.println(maxLength2(arr));
138 }
139 }
//http://blog.csdn.net/code_pang/article/details/8757380
//http://blog.csdn.net/chenwenshi/article/details/6027086