문제
수열 A가 주어질 때, 그 수열의 증가하는 부분 수열 중 원소의 합이 가장 큰 것의 합을 구하는 문제다. LIS(가장 긴 증가하는 부분 수열)는 길이 기준이지만, 이 문제는 원소의 합 기준으로 최대를 구한다는 점이 다르다.
입력
- 첫째 줄: 수열의 크기 N (1 ≤ N ≤ 1000)
- 둘째 줄: N개의 정수 A[i] (1 이상 1000 이하)
출력
가장 큰 증가하는 부분 수열의 합을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 1 100 2 50 60 | 211 |
풀이
dp[n]을 n번째 원소를 마지막으로 하는 증가 부분 수열의 최대 합으로 정의하고 Top-Down 메모이제이션으로 계산한다. LIS 문제에서 길이 대신 합을 누적하는 방식이다.
recur(n)함수는 n번째 원소를 마지막으로 하는 증가 부분 수열의 최대 합을 반환한다.dp[n]이 null이면arr[n]으로 초기화한다 (자기 자신만 포함하는 수열).i < n이고arr[n] > arr[i]인 모든 i에 대해max(dp[n], recur(i) + arr[n])을 계산하여 저장한다.- 모든 n에 대해
recur(n)을 호출하고 그 결과 중 최댓값이 답이다.
핵심 아이디어: LIS와 동일한 구조의 점화식에서 길이 +1 대신 현재 원소의 값 arr[n]을 더해 합을 누적한다. dp[n] = max(dp[i] + arr[n]) (단, i < n이고 arr[i] < arr[n])으로 표현된다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Day83BOJ11055가큰증부수DP { // 11055 가장 큰 증가 부분 수열
static int N, ans;
static int[] arr;
static Integer[] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
arr = new int[N];
dp = new Integer[N];
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++)
ans = Math.max(ans, recur(i));
System.out.println(ans);
br.close();
}
private static int recur(int n) {
// System.out.println(Arrays.toString(dp).replaceAll("ull", ""));
if (n == -1)
return 0;
if (dp[n] != null)
return dp[n];
dp[n] = arr[n];
for (int i = n - 1; i >= 0; i--)
if (arr[n] > arr[i])
dp[n] = Math.max(dp[n], recur(i) + arr[n]);
return dp[n];
}
}복잡도
- 시간: O(N^2) — 각 원소마다 이전 원소를 모두 확인
- 공간: O(N) — dp 배열과 입력 배열 각각 N 크기