문제

BOJ 11055, 가장 큰 증가하는 부분 수열

핵심

• 입력의 크기가 $10^3$이라 구현에 초점을 맞춘다.
• 수열 A가 주어질 때 증가하는 부분 수열 중 합이 가장 큰 것을 구해야 한다.
• 핵심 아이디어는 수열에 각 위치에서 끝나는 증가 부분 수열의 합을 구한 뒤 원소 간의 비교를 통해 작은 부분 수열의 합을 큰 곳에 이어 붙이는 것이다. 쉽게 예를 들어 설명하면 [1, 30, 2, 50, 4] 이러한 수열이 있을 때 1은 30보다 작으니 1로 끝나는 부분수열을 30에 이어붙여 [1, 30]을 만들 수 있고 다시 [1, 30]을 50에 이어붙여 [1, 3, 50]을 만들 수 있다.
• dp[i]: i번째 수를 마지막으로 하는 증가하는 부분 수열이다. num[j]가 더 적다면 num[j]를 마지막으로 하는 증가 부분 수열을 num[i]에 이어 붙인다. 위의 예시를 보고 눈으로 따라가보면 이해할 수 있다.

if (num[j] < num[i])
	dp[i] = max(dp[i], dp[j] + nums[i]);

개선

코드

시간복잡도

• $O(N^2)$

C++

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1004];
int nums[1004];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> nums[i];
		dp[i] = nums[i];
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j < i; ++j) {
			if (nums[j] < nums[i])
				dp[i] = max(dp[i], dp[j] + nums[i]);
		}
	}
	cout << *max_element(dp + 1, dp + n + 1);
}

Java

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

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[] nums = new int[n + 4];
        int[] dp = new int[n + 4];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            dp[i] = nums[i];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; ++j) {
                if (nums[j] < nums[i])
                    dp[i] = Math.max(dp[i], dp[j] + nums[i]);
            }
        }
        int mx = 0;
        for (int i = 1; i <= n; i++) {
            if (dp[i] > mx)
                mx = dp[i];
        }
        System.out.println(mx);
        br.close();
    }
}