(Hacker Rank) The Longest Increasing Subsequence - Solution

Link to the problem: https://www.hackerrank.com/challenges/longest-increasing-subsequent

The solution below used the concept of Longest Increasing Subsequence (LIS), related to Dynamic Programming, to solve this problem.


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numNumbers = sc.nextInt();
        Info[] numbers = new Info[numNumbers];
        for (int i = 0; i < numNumbers; i++) {
            numbers[i] = new Info(sc.nextInt(), 0);
        }
       
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < numNumbers; i++) {
            Map.Entry<Integer, Integer> entry = map.ceilingEntry(numbers[i].number);
            if (entry == null) {
                numbers[i].lis = map.size()+1;
                map.put(numbers[i].number, map.size()+1);
            }
            else {
                numbers[i].lis = entry.getValue();
                map.remove(entry.getKey());
                map.put(numbers[i].number, entry.getValue());
            }
        }
       
        int maxSubsequence = 0;
        for (int i = 0; i < numNumbers; i++) {
            maxSubsequence = Math.max(maxSubsequence, numbers[i].lis);
        }
       
        System.out.println(maxSubsequence);
    }
}

class Info {
    int number;
    int lis;
   
    public Info(int n, int l) {
        number = n;
        lis = l;
    }
}