I was recently working on the following problem.

http://www.codechef.com/problems/D2

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 :