[C++] 백준 11055번 : 가장 큰 증가 부분 수열 (S2)

#문제

www.acmicpc.net/problem/11055

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

#풀이 & 학습한 내용

supremo7.tistory.com/92에서는 길이를 구했다면, 이 문제에서는 수의 합에 대해 살핀다. 따라서 맨 처음 그 수만 포함할때인 p[i]를 dp[i]에 저장하고, 그 앞의 수들에 대해 p[j] < p[i] && dp[j] + p[i] > dp[i]를 통해 dp[i]를 갱신하며 결정한다. 그리고 dp배열의 값들 중 최댓값을 결과로 출력해준다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int p[1002];
int dp[1002];
 
int main(void) {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> p[i];
    //input end
 
    for (int i = 1; i <= N; i++) {
        dp[i] = p[i];
        for (int j = 1; j <= i; j++) {
            if (p[j] < p[i] && dp[j] + p[i] > dp[i]) {
                dp[i] = dp[j] + p[i];
            }
        }
    }
 
    int max = dp[1];
    for (int i = 2; i <= N; i++) {
        if (max < dp[i])
            max = dp[i];
    }
    cout << max << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_11055.cpp

HoYoungChun/BOJ_algorithm