Algorithm-and-Data-Structure/AlgorithmCode/LongestIncreasingSubSequence.java at master · lemidia/Algorithm-and-Data-Structure · GitHub

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
47
48
49
50
51
52
53
54
55
56
57
importjava.util.Arrays;
importjava.util.LinkedList;

publicclassLongestIncreasingSubSequence {

publicstaticvoidLIS(intarr[]) {
if (arr.length == 0)
return;
intdp[] = newint[arr.length];
intsequence[] = newint[arr.length];
intlongestLength = 1;
intlongestLengthPosition = -1;

Arrays.fill(dp, 1);
for (inti = 0; i < sequence.length; i++) {
sequence[i] = i;
 }

for (inti = 1; i < arr.length; i++) {
for (intj = 0; j < i; j++) {
if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
if (longestLength < dp[i]){
longestLength = dp[i];
longestLengthPosition = i;
 }
sequence[i] = j;
 }
 }
 }

System.out.println("LIS is " + longestLength);

LinkedList<Integer> list = newLinkedList<>();

inti = longestLengthPosition;

for ( ; i != sequence[i]; i = sequence[i]) {
list.addFirst(arr[i]);
 }

list.addFirst(arr[i]);

System.out.print("Sub Sequence is ");

for (intnext : list)
System.out.print(next + " ");

 }
publicstaticvoidmain(String[] args) {
intarr1 [] = {2, 4, 1, 5, 10, 14, 0, 7, 9, 11, 17};
// Output:
// LIS is 7
// Sub Sequence is 2 4 5 7 9 11 17
LIS(arr1);
 }
}