@@ -17,7 +17,6 @@ public static void main(String[] args) {
1717System .out .println (LIS (arr ));
1818System .out .println (findLISLen (arr ));
1919sc .close ();
20-
2120 }
2221
2322private static int upperBound (int []ar ,int l ,int r ,int key ) {
@@ -58,40 +57,33 @@ private static int LIS(int[] array) {
5857
5958return length ;
6059 }
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- }
60+
61+ /** @author Alon Firestein (https://github.com/alonfirestein) */
62+
63+ // A function for finding the length of the LIS algorithm in O(nlogn) complexity.
64+ public static int findLISLen (int a []) {
65+ int size =a .length ;
66+ int arr [] =new int [size ];
67+ arr [0 ] =a [0 ];
68+ int lis =1 ;
69+ for (int i =1 ;i <size ;i ++) {
70+ int index =binarySearchBetween (arr ,lis ,a [i ]);
71+ arr [index ] =a [i ];
72+ if (index >lis )lis ++;
73+ }
74+ return lis ;
75+ }
7876// 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-
77+ private static int binarySearchBetween (int []t ,int end ,int key ) {
78+ int left =0 ;
79+ int right =end ;
80+ if (key <t [0 ])return 0 ;
81+ if (key >t [end ])return end +1 ;
82+ while (left <right -1 ) {
83+ int middle = (left +right ) /2 ;
84+ if (t [middle ] <key )left =middle ;
85+ else right =middle ;
86+ }
87+ return right ;
88+ }
9789}
