I was recently working on the following problem.
Let me brief it for you.
We have a round table with N(1<= N <= 10000) people sitting holding random numbers. We need to find the maximum length of Longest Increasing Subsequence.
For eg.
input : 5 6 7 8 1 2 3 4
7
6 8
5 1
4 2
3
output should be 8. Bcoz if we start from 1, we can get the maximum LIS as 1 2 3 4 5 6 7 8, i.e of lenght 8.
You can go through the link to get the problem more correctly.
My solution is based on following steps:
to create an array twice the length
eg for the above array, my array would be 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4
Now, for (i = 0 to N-1), Ill calculate the LIS for next N elements using nlog(n).
So the overall complexity will me n^2log(n).
But this is not accepted by the judge. Getting TLE.
Can someone suggest any improvements on this.
public class D2 {
private static int getCiel(int a[],int val,int l, int r){
int m = 0;
while (l<r-1){
m = l+(r-l)/2;
if(a[m]>val){
r = m;
}else{
l=m;
}
}
return r;
}
private static int getLIS(int[] a, int startIndex,int N) { //this calculates LIS for elements in array starting from startIndex upto N elements.
int length = 1;
int [] lists = new int[a.length-1];
lists[0] = a[startIndex];
for (int i = 1;i<N;i++){
if(a[i+startIndex]><lists[0]){
lists[0]=a[i+startIndex];
}
else if(a[i+startIndex]>lists[length-1]){
lists[length++]=a[i+startIndex];
}
else{
lists[getCiel(lists,a[i+startIndex],0,length-1)] = a[i+startIndex];
}
}
return length;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
InputReader in = new InputReader(System.in);
int TC = in.readInt();
while (TC-- > 0) {
int N = in.readInt();
int [] numbers = new int[2*N+1];
for(int i = 0;i<N;i++){
numbers[i] = in.readInt();
numbers[i+N] = numbers[i];
}
int max = 0;
for(int i = 0;i<N;i++){
max = max(max,getLIS(numbers,i,N));
}
pw.println(max);
}
pw.flush();
pw.close();
}
private static int max(int n1, int n2) {
return (n1>n2?n1:n2);
}
}
The solution that I wrote :