本文實例講述了java實現求數組最長子序列算法。分享給大家供大家參考，具體如下：
問題：給定一個長度為n的數組，找出一個最長的單調自增子序列（不一定連續，但是順序不能亂） 例如：給定一個長度為8的數組a{1，3，5，2，4，6，7，8}，則其最長的單調遞增子序列為{1，2，4，6，7，8}，長度為6。
思路1：第一眼看到題目，很多人肯定第一時間想到的是lcs。先給數組排個序形成新數組，然后再把新數組和原數組拿來求lcs，即可得到答案。這種解法很多人能想得到，所以就不再贅述。
思路2：按照思路1的想法，最后求lcs時還是得用到dp，我們干嘛不直接用dp來求解呢。對于數組arr，我們從后往前遍歷數組，分別求出當子序列以arr[i]結尾時的最長子序列，然后取其中的最大值。即可得到整個數組的最長子序列。 那么怎么求以arr[i]結尾時的最長子序列呢，這就轉換成一個dp問題了。要求arr[i]的最長子序列，只需要求出arr[i-1]的最長子序列。即：max{arr[i]}=max{arr[i-1]}+1。
java實現代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
public class arrdemo { public static void main(string[] args) { // int[] arr = {89, 256, 78, 1, 46, 78, 8}; int[] arr = { 1, 3, 5, 2, 4, 6, 7, 8 }; // int[] arr = {6, 4, 8, 2, 17}; int max = 0; int maxlen = arr.length; // 從后往前遍歷數組，分別求出以arr[i]結尾的時候的最長子序列長度 for (int i = arr.length - 1; i > 0; i--) { int[] newarr = new int[i]; system.arraycopy(arr, 0, newarr, 0, i); int currentlength = 1 + dp(newarr, arr[i]); if (currentlength > max) max = currentlength; // 最長子序列的長度最長為原始數組的長度， // 因為不需要我們求最長子序列的元素，所以直接結束循環，減少時間開銷 if (max == maxlen) break; } system.out.println(max); } public static int dp(int[] arr, int end) { // 遞歸結束條件 if (arr.length == 1) { // 小于end則包含在子序列中，子序列長度+1 if (arr[0] <= end) return 1; else return 0; } // 遍歷數組，找到最靠近end的并且<=end的元素位置i for (int i = arr.length - 1; i >= 0; i--) { if (arr[i] <= end) { // 從i處截斷數組，將arr[0]到arr[i-1]組成新數組繼續遞歸求長度 int[] newarr = new int[i]; system.arraycopy(arr, 0, newarr, 0, i); // 分別計算包含arr[i]時的最長子序列和不包含arr[i]時的最長子序列，取最大值 int containlen = dp(newarr, arr[i]) + 1; int notcontainlen = dp(newarr, end); return containlen > notcontainlen ? containlen : notcontainlen; } } // 如果沒找到比end更小的，返回長度為0 return 0; }} |
運行結果：
6
我的方法由于中間開辟了多個新數組，可能占用的空間有點多，不過我覺得應該也不是很多- -，具體我也沒統計過。如果有不對的地方還請指正。
希望本文所述對大家java程序設計有所幫助。
原文鏈接：https://blog.csdn.net/ztzy520/article/details/78018321
