LIS(Longest Increasing Subsequence) 최대 부분 증가 수열

LIS란?

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다.

예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이 됩니다.
{ 2, 5 }, { 2, 7 } 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 { 2, 5, 7, 8 } 입니다.

입력 설명

첫째 줄은 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)를 의미하고,

둘째 줄은 N개의 입력데이터들이 주어진다.

출력 설명

첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

입력

8
5 3 7 8 6 2 9 4

출력

4

구현 코드

public class 최대부분증가수열 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); //숫자 개수
        int[] arr = new int[n]; //숫자 배열
        Integer[] dy = new Integer[n]; 
        //i번째 숫자를 마지막항으로 하는 최대 증가수열의 길이 담는 배열

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

        for(int i=0;i<n;i++){
            int maxLength = 0;
            for(int j = i;j>=0;j--){
                //감소하며 비교
                if(arr[i]>arr[j]){
                    if(maxLength<dy[j]){
                        maxLength = dy[j];
                    }
                }
            }
            dy[i] = maxLength + 1;
        }

        Arrays.sort(dy,Collections.reverseOrder());
        System.out.println(dy[0]);
    }

}

처음에 문제를 읽었을 때 잘못 이해해서 애를 먹었음. 주어진 순서에 상관 없이 정렬해서 만들 수 있는 연속된 수열의 최대길이를 구하라는 줄 이해해서, 답이 왜 저렇게 나오는지 이해를 못했음.
하지만 정해진 순서를 건들지 않은채 만드는 것 였음.

• 알고리즘

  arr : 숫자 배열
  dy : i번째 숫자를 마지막항으로 하는 최대 증가수열의 길이 담는 배열
  maxLength : i 이전의 항들의 dy값 중 최대 길이 담는 변수
  이중 for i : 0~n-1 증가
  j : i~0 감소
  arr[i]>arr[j] -> 증가하는 조건 확인
  maxLength<dy[j] -> 최대길이를 찾기
  j for 끝날 시 dy[i]
  arr[i]>arr[j]인 경우 -> 1
  arr[i]<arr[j]인 경우 -> maxLength + 1
  dy에서 최대값 출력

참고

LIS