GeezerVison is showing github.com — Update LongestIncreasingSubsequence.java · JavaInCloud/Java@4e70451
File tree
Expand file treeCollapse file tree
Open diff view settings
Expand file treeCollapse file tree
Open diff view settings
Collapse file
Copy file name to clipboardExpand all lines: DynamicProgramming/LongestIncreasingSubsequence.java +41-3Lines changed: 41 additions & 3 deletions | Original file line number | Diff line number | Diff line change |
|---|
@@ -9,13 +9,15 @@ public static void main(String[] args) { |
9 | 9 | Scanner sc = new Scanner(System.in); |
10 | 10 | int n = sc.nextInt(); |
11 | 11 |
|
12 | | - int ar[] = new int[n]; |
| 12 | + int arr[] = new int[n]; |
13 | 13 | for (int i = 0; i < n; i++) { |
14 | | - ar[i] = sc.nextInt(); |
| 14 | + arr[i] = sc.nextInt(); |
15 | 15 | } |
16 | 16 |
|
17 | | - System.out.println(LIS(ar)); |
| 17 | + System.out.println(LIS(arr)); |
| 18 | + System.out.println(findLISLen(arr)); |
18 | 19 | sc.close(); |
| 20 | + |
19 | 21 | } |
20 | 22 |
|
21 | 23 | private static int upperBound(int[] ar, int l, int r, int key) { |
@@ -56,4 +58,40 @@ private static int LIS(int[] array) { |
56 | 58 |
|
57 | 59 | return length; |
58 | 60 | } |
| 61 | + |
| 62 | + /** @author Alon Firestein (https://github.com/alonfirestein) */ |
| 63 | + |
| 64 | + // A function for finding the length of the LIS algorithm in O(nlogn) complexity. |
| 65 | + public static int findLISLen(int a[]) { |
| 66 | + int size = a.length; |
| 67 | + int arr[] = new int[size]; |
| 68 | + arr[0] = a[0]; |
| 69 | + int lis = 1; |
| 70 | + for (int i = 1; i < size; i++) { |
| 71 | + int index = binarySearchBetween(arr, lis, a[i]); |
| 72 | + arr[index] = a[i]; |
| 73 | + if (index > lis) |
| 74 | + lis++; |
| 75 | + } |
| 76 | + return lis; |
| 77 | + } |
| 78 | + // O(logn) |
| 79 | + private static int binarySearchBetween(int[] t, int end, int key) { |
| 80 | + int left = 0; |
| 81 | + int right = end; |
| 82 | + if (key < t[0]) |
| 83 | + return 0; |
| 84 | + if (key > t[end]) |
| 85 | + return end + 1; |
| 86 | + while (left < right - 1) { |
| 87 | + int middle = (left + right) / 2; |
| 88 | + if (t[middle] < key) |
| 89 | + left = middle; |
| 90 | + else |
| 91 | + right = middle; |
| 92 | + } |
| 93 | + return right; |
| 94 | + } |
| 95 | + |
| 96 | + |
59 | 97 | } |