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

문제 링크입니다 https://www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

'11053번 가장 긴 증가하는 부분 수열' 문제(https://seokeeee.tistory.com/61)와 유사한 문제였습니다. "dp[N] : 크기가 N인 수열에서 가장 큰 증가하는 부분 수열의 합"이라고 정의하고 문제를 해결했습니다. 위 링크 참조해주세요!

 

 

[소스코드]

 

#include<cstdio>
 
int n, num[1000], dp[1000];
 
int main(void) {
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &num[i]);
 
    // dp[0]부터 dp[n-1]까지의 값을 결정합니다
    for (int i = 0; i < n; i++) {
        dp[i] = num[i]; // 자기 자신이 가장 큰 증가 부분 수열
 
        // 현재 칸보다 왼쪽에 있는 모든 칸에 대해
        for (int j = 0; j < i; j++) {
 
            // 현재 칸보다 왼쪽에 있는 칸의 수가 더 작고, 결정한 dp[i]값이
            // j번째 칸 까지의 가장 큰 증가 부분 수열 + 현재 칸 보다 작다면
            // 현재 칸의 값을 j번째 칸 까지의 가장 큰 증가 부분 수열 + 현재 칸으로 update
            if (num[j] < num[i] && dp[i] < dp[j] + num[i]) {
                dp[i] = dp[j] + num[i];
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (ans < dp[i]) ans = dp[i];
    }
    printf("%d", ans);
    return 0;
}