(UVA) What Goes Up - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=422

The solution below uses a modified version of the Longest Increasing Sequence (LIS).


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

class Main {
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        ArrayList<Feature> numbers = new ArrayList<>();
        String line = br.readLine();
        while (line != null) {
            numbers.add(new Feature(Integer.parseInt(line), -1));
            line = br.readLine();
        }
        br.close();
       
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < numbers.size(); i++) {
            Map.Entry<Integer, Integer> entry = map.ceilingEntry(numbers.get(i).number);
            if (entry == null) {
                numbers.get(i).index = map.size()+1;
                map.put(numbers.get(i).number, map.size()+1);
            }
            else {
                numbers.get(i).index = entry.getValue();
                map.remove(entry.getKey());
                map.put(numbers.get(i).number, entry.getValue());
            }
        }
       
        int index = map.size();
        int[] answer = new int[map.size()];
        int nextNumber = 2000000000;
        for (int i = numbers.size()-1; i >= 0; i--) {
            if (numbers.get(i).index == index && numbers.get(i).number < nextNumber) {
                answer[index-1] = numbers.get(i).number;
                nextNumber = answer[index-1];
                index--;
            }
        }
       
        bw.write(map.size()+"\n-\n");
        for (int i = 0; i < answer.length; i++) {
            bw.write(answer[i]+"\n");
        }
           
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Feature {
    int number;
    int index;
   
    public Feature(int n, int i) {
        number = n;
        index = i;
    }
}