백준 11055 가장 큰 증가 부분 수열

https://www.acmicpc.net/problem/11055

문제해결

가장 긴 증가하는 부분 수열 (LIS) 문제의 응용 버전이다. https://www.acmicpc.net/problem/11053

먼저, 점화식은 D[i] = i번째에서 끝나는 부분 수열의 합으로 정의하였다.
i번째에 A[i]가 있다면 i-1번째에는 어떤 수가 올까? 어떤 수가 올 지 모르니 A[j]라는 변수를 선언하자. 다시 j번째에 A[j]가 있다면 j번째에서 끝나는 부분 수열의 합은 D[j]가 되고 최종 점화식은 D[i] = max(D[j] + A[i]) 가 된다. 이 때 j < i, A[j] < A[i] 다음과 같은 조건을 만족해야 한다.
초기값으로 자기 자신을 정의해주었고 코드는 다음과 같다.

정확하게 어떤 문제인지 기억은 안나지만 Math 클래스의 max() 메소드를 이용했더니 시간초과가 나서 비교 연산자를 이용해서 최댓값을 변경해주었다.

소스코드

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

/**
 * LIS 응용
 */

public class b11055 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        int[] dp = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < n; i++) {
            dp[i] = a[i];
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i] && dp[i] < dp[j] + a[i]) {
                    dp[i] = dp[j] + a[i];
                }
            }
        }
        // 최댓값 찾기
        int ans = dp[0];
        for (int i = 0; i < n; i++) {
            if (ans < dp[i]) {
                ans = dp[i];
            }
        }
        System.out.println(ans);
    }
}