[JAVA] 백준 q11053 - 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열

---

> 의식의 흐름
수열의 크기가 최대 1,000이니까 O(N^2) 가능하겠넹..? 그럼 전체 다 훑어봐야지~

> 풀이 과정
1. 수열의 크기(N)을 입력 받는다.
2. 수열을 배열(nums)에 입력받고 수열의 길이를 저장하는 배열(arrCnt)를 1로 초기화한다.
3. nums[i]와 뒤쪽 수(nums[j])를 비교한다
- 만약 nums[i] < nums[j]인 경우, 증가하는 수열이 되므로 `arrCnt[j] = arrCnt[i]+1`로 변경한다.
하지만 이때 arrCnt[j] > arrCnt[i]+1인 경우, 가장 긴 수열을 구해야하는 것이므로 arrCnt[j] 값을 그대로 두어야 한다. 
=> arrCnt[j] = Math.max(arrCnt[i]+1, arrCnt[j]);

for(int i=0;i<N-1;i++){
      int leastNum = nums[i];

      for(int j=i;j<N;j++){
            if(leastNum<nums[j]){ // 증가하는 수인 경우
                  arrCnt[j] = Math.max(arrCnt[i]+1, arrCnt[j]);
            }
      }
}

4. 3번 과정에서 업데이트된 arrCnt에서 가장 큰 값이 가장 긴 증가하는 부분 수열의 길이이므로 해당 값을 출력한다.

 

> 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N; // 수열의 크기
    public static int[] nums; // 수열
    public static int[] arrCnt; // 부분 수열 길이

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        nums = new int[N];
        arrCnt = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            nums[i] = Integer.parseInt(st.nextToken());
            arrCnt[i] = 1;
        }

        for(int i=0;i<N-1;i++){
            int leastNum = nums[i];

            for(int j=i;j<N;j++){
                if(leastNum<nums[j]){ // 증가하는 수인 경우
                    arrCnt[j] = Math.max(arrCnt[i]+1, arrCnt[j]);
                }
            }
        }

        int ans = 0;
        for(int i=0;i<N;i++){
            ans = Math.max(ans, arrCnt[i]);
        }

        bw.write(Integer.toString(ans));
        bw.flush();

        br.close();
        bw.close();
    }
}