Java longest increasing subsequence: tails are search state

Java 8+. The program uses JDK classes and requires no preview flags.

Interpret the tails array correctly

The tails array keeps the smallest known tail value for each achieved subsequence length. It is search state. Its entries can come from different subsequences, so printing that array does not reconstruct one selected solution.

A lower-bound search replaces the first tail greater than or equal to the incoming value. Equal values therefore do not extend the strictly increasing length. A non-decreasing problem uses a different boundary; changing that comparison changes the contract.

Negative values and integer extremes need no subtraction-based comparator. Direct comparisons avoid overflow when the distance between values exceeds the int range. The input remains unchanged because only the separate tails array is modified.

Choose reconstruction separately

If a caller needs actual indices, store predecessor indices and which input position currently represents each tail. That extra state has a purpose: reconstructing one valid solution. Keep a deterministic tie policy if the displayed solution matters to users.

Working program

public class ArrivalIncreasingOrder {
    static int length(int[] values){
        int[] tails=new int[values.length];int used=0;
        for(int value:values){
            int low=0,high=used;
            while(low<high){int middle=low+(high-low)/2;if(tails[middle]<value)low=middle+1;else high=middle;}
            tails[low]=value;if(low==used)used++;
        }return used;
    }
    public static void main(String[] args){System.out.println(length(new int[]{7,3,5,5,8,1,9}));System.out.println(length(new int[]{4,4,4}));System.out.println(length(new int[0]));}
}

Output

4
1
0

Costs and boundaries

Time is O(n log n); the tails array uses O(n) storage. A simple O(n²) reference is useful for verifying small inputs independently. This implementation returns only the length and never mutates the input array.

Common Mistakes

• The tails array is not necessarily the selected subsequence.
• Strictly increasing and non-decreasing use different equal-value handling.
• Do not compare by subtracting arbitrary int values.

Read next

Boundary search, Sequence order.