[백준/DP/C++] 11055번 가장 큰 증가 부분 수열

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

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

dp는 수열 a와 같이 초기화해준다

전의 수열 값과 비교하면서 자신의 값보다 작으면 그 값의 dp값에 자신의 값을 더한 것과 자신의 dp값을 비교해 더 큰 값을 넣어주면 된다

#include <bits/stdc++.h>

using namespace std;
int n;
int dp[1001] = {0}, a[1001] ={0};

int main(void) {
    cin >> n;

    for(int i=1; i<=n; i++){
        cin >> a[i];
        dp[i] = a[i];
    }

    for(int i=2; i<=n; i++){
        for(int j=1; j<i; j++){
            if(a[i]>a[j])
                dp[i] = max(dp[i], dp[j]+a[i]);
        }
    }

    int result = 0;
    for(int i=1; i<=n; i++)
        result = max(result, dp[i]);
    cout << result << endl;

    return 0;
}

반응형