# D2: Need help in optimizing a solution

For the lucky draw problem, I have written a java solution with a complexity of `O(NlogN)` but even this gives a Time limit exceeded error.
How can I further optimize my solution to get it to pass.

``````import java.io.*;
import java.util.*;

public class D2
{
public static void main(String [] args)
throws IOException
{
for(int _t=0; _t<numTestCases; ++_t)
{
int [] originalArray = new int[N*2];
for(int i=0; i<N; ++i)
{
//this concatenates the array with itself at the time of reading the input itself
originalArray[i] = originalArray[N+i] = Integer.parseInt(strtok.nextToken());
}
//Now we calculate the length of the longest increasing sequence
int maxWinners = new LongestIncreasingSequence(originalArray).lengthOfLongestIncreasingSequence();
System.out.println(maxWinners);
}
}
}

class LongestIncreasingSequence
{
int [] array;
private ArrayList<Integer> longest;
public LongestIncreasingSequence(int [] A)
{
array = A;
longest = new ArrayList<Integer>();
}

public int lengthOfLongestIncreasingSequence()
{
for(int i=1; i<array.length; ++i)
{
if(array[i] < longest.get(0))
{
longest.set(0,array[i]);
}
else if(array[i] > longest.get(longest.size()-1))
{
}
else
{
//Make the replacement with binary search
longest.set(getReplacementIndex(array[i]),array[i]);
}
}
return longest.size();
}

//Method to find the correct index using binary search
private int getReplacementIndex(int elem)
{
int left, right, mid;
left = 0; right = longest.size() - 1;
while(right - left > 1)
{
mid = 1 + (right - left) / 2;
if(array[mid] >= elem)
{
if(mid != right) right = mid;
else --right;
}
else
{
left = mid;
}
}
return right;
}
}
``````

``````    final int[] a = { 1, 2, 3 };
and it prints `[1]`, I think this is not correct. Did I missed something?