-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLongestSubSequence.java
More file actions
59 lines (52 loc) · 1.44 KB
/
LongestSubSequence.java
File metadata and controls
59 lines (52 loc) · 1.44 KB
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
58
59
package algorithm.DynamicProgramming;
import java.util.Arrays;
/**
* The type Longest sub sequence.
*/
public class LongestSubSequence {
/**
* Gets longest sub sequence.
*
* @param arr the arr
* @param n the n
* @return the longest sub sequence
*/
public static int getLongestSubSequence(int[] arr, int n) {
int dp[][] = new int[n + 1][n + 1];
for (int[] row : dp)
Arrays.fill(row, -1);
return util(0, -1, n, arr, dp);
}
/**
* Util int.
*
* @param idx the idx
* @param pridx the pridx
* @param n the n
* @param arr the arr
* @param dp the dp
* @return the int
*/
private static int util(int idx, int pridx, int n, int[] arr, int[][] dp) {
if (idx == n)
return 0;
else if (dp[idx][pridx + 1] != -1)
return dp[idx][pridx + 1];
int notTake = 0 + util(idx + 1, pridx, n, arr, dp);
int take = Integer.MIN_VALUE;
if (arr[pridx + 1] > arr[idx] || pridx == -1)
take = 1 + util(idx + 1, idx, n, arr, dp);
return dp[idx][pridx + 1] = Math.max(notTake, take);
}
/**
* Main.
*
* @param args the args
*/
public static void main(String args[]) {
int a[] = {3, 10, 2, 1, 20};
int n = a.length;
// Function call
System.out.println("Length of lis is " + getLongestSubSequence(a, n));
}
}