# Optimizing solution for The Lucky Draw problem.

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 = a[startIndex];

for (int i = 1;i<N;i++){
if(a[i+startIndex]><lists){
lists=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 {
PrintWriter pw = new PrintWriter(System.out);

while (TC-- > 0) {
int [] numbers = new int[2*N+1];
for(int i = 0;i<N;i++){
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 :

I’m also getting WA in this question.
this is my solution