최대 부분 증가 수열(LIS)

N개의 자연수로 이루어진 수열에서 작은수에서 가장 큰수로 증가하는 원소들의 집합 중에서 가장 큰 길이를 찾아라

ex)
원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면
가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12이고
문제의 답은 5이다.

입력) 수열의 개수 N과 수열
8
5 3 7 8 6 2 9 4

출력)
4

import java.util.Scanner;

public class Main {

    static int n;
    static int[] arr;
    static int[] answer;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        arr = new int[n];
        answer = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        System.out.println(getMaxLength());
    }

    private static int getMaxLength() {
        int max = 1;
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            int value = arr[i];
            answer[i] = 1;

            for (int j = i - 1; j >= 0; j--) {
                if (value > arr[j]) {
                    answer[i] = Math.max(answer[i], answer[j] + 1);
                }
            }
            max = Math.max(max, answer[i]);
        }

        return max;
    }
}