[Java] 백준 가장 큰 부분 수열

1. 문제분석

부분 수열의 합 중에 가장 큰 수를 구하는 문제다.

증가하는 부분 수열이어야 하니 a[j] < a[i]
만약 조건에 맞을 때는 dp테이블에 저장된 값을 가져와 더해주면 된다.

2. 구현

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int dp[] = new int[N+1];
		int map[] = new int[N+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			map[i] = Integer.parseInt(st.nextToken());
			dp[i] = map[i];
		}
		int result = dp[1];
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<i; j++) {
				if(map[j] < map[i]) {
					dp[i] = Math.max(dp[j]+map[i], dp[i]);
					result = Math.max(result, dp[i]);
				}
			}
		}
		System.out.println(result);
		br.close();
	}

}

 

3. 마무리

ㅇDP는 정말 풀어도 이해가 가지 않는다.
그래도 이번에 LIS가 뭔지 알았으니 계속 이어나가야 겠다.