백준 15966 군계일학

효빈이는 어떤 수열에서 군계일학 수열을 뽑아내고자 한다. 단, 뽑은 항의 순서는 기존 수열에서의 순서를 유지해야 한다. 군계일학 수열은 각 항이 서로 연속적인 수열을 의미한다. 정확한 정의는 다음과 같다.

수열 중에 어떤 임의의 항 i에 대해서, ai=a1+(i-1)을 만족해야한다.

길이가 N이고 정수로 이루어진 수열이 주어진다. 효빈이는 가장 긴 군계일학 수열을 가져가서 김승호 선생님께 자랑하려고 한다. 효빈이가 뽑아낼 수 있는 가장 긴 군계일학 수열의 크기를 출력하라.

입력
첫째 줄에 수열의 길이 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에, ai (1 ≤ i ≤ N, 1 ≤ ai ≤ 1,000,000)이 주어진다.

출력
수열에서 뽑아낼 수 있는 가장 긴 군계일학 수열의 길이를 출력한다.

1. 이 수열은 1씩 늘어나는 등차 수열이다. 
2. 그러므로 항상 단조 증가하고 자기 자신보다 더 작은 수는 오른편에 올 수 없다.
3. 10만개이므로 for문 1개와 1차원 배열 1개로 해결해야 한다.
4. DP를 쓰는데 그 전 값의 idx가 필요하기 때문에 
Map을 사용하여 idx를 기록 해준다 
5. 현재 값 - 1한것이 map에 기록되어있다면 수열의 길이는 1증가하고 메모라이제이션 해준다
 - 만약에 현재 값 - 1한것이 없다면 현재값이 만들 수 있는 수열의 가장 작은 값이기 때문에 Map에 등록해준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int array[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer :: parseInt).toArray();
        int DP[] = new int[N];
        
        // N이 1일때는 1개가 최고 긴 길이다
        if(N == 1) {
            System.out.println(1);
            return;
        }


        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(array[0], 0);
        DP[0] = 1;
        int result = Integer.MIN_VALUE;
        for(int i = 1; i < N; i++) {
            // Map 체크
            if(map.containsKey(array[i] - 1)) {
                DP[i] = DP[map.get(array[i] - 1)] + 1;
                map.put(array[i], i);
            } else {
                DP[i] = 1;
                map.put(array[i], i);
            }
            
            // 수열길이 최대값 갱신
            if(result < DP[i]) {
                result = DP[i];
            }

        }


        System.out.println(result);
    }

}