[백준] 가장 큰 증가 부분 수열 (!) (11055번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

[백준] 가장 큰 증가 부분 수열 (!) (11055번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

---

[접근 방법]

LIS 문제와 비슷하다곤 하지만, 나에겐 굉장히 어려운 문제였다.

LIS는 DP 배열에 원소간의 대소 관계를 이용한 일종의 서열을 저장해 두었지만,

이번 문제에는 본인을 마지막으로 하는 증가 수열 중 가장 큰 수열원소의 합을 저장한다.

 

인덱스 4의 경우,

[1, 2, 50]의 증가 부분 수열을 가지고 있다.

인덱스 5를 고려하기 위해서

DP의 인덱스 4에 이전 인덱스 중 가장 큰 수열원소의 합을 미리저장해 놓으면 편할 것이다.

 

완벽히 이해를 하지 못해 더이상의 설명은 어렵다.

---

[JAVA 코드]

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

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 수열 A의 크기 N (1 ≤ N ≤ 1,000)
        int N = Integer.parseInt(br.readLine());

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

        DP[1] = A[1];

        int result = DP[1];
        for(int i=2; i<N+1; i++){
            DP[i] = A[i];
            for(int j=1; j<i; j++){
                if (A[i] > A[j]){
                    DP[i] = Math.max(DP[i], DP[j] + A[i]);
                }
            }

            // 가장 큰 증가 부분 수열 원소의 합 갱신
            result = Math.max(result, DP[i]);
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}