@@ -9,13 +9,15 @@ public static void main(String[] args) {
99Scanner sc =new Scanner (System .in );
1010int n =sc .nextInt ();
1111
12- int ar [] =new int [n ];
12+ int arr [] =new int [n ];
1313for (int i =0 ;i <n ;i ++) {
14- ar [i ] =sc .nextInt ();
14+ arr [i ] =sc .nextInt ();
1515 }
1616
17- System .out .println (LIS (ar ));
17+ System .out .println (LIS (arr ));
18+ System .out .println (findLISLen (arr ));
1819sc .close ();
20+
1921 }
2022
2123private static int upperBound (int []ar ,int l ,int r ,int key ) {
@@ -56,4 +58,40 @@ private static int LIS(int[] array) {
5658
5759return length ;
5860 }
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+
5997}