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

문제

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

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

 

이 문제랑 굉장히 유사함
2022.01.19 - [PS/Baekjoon] - [백준/C++] 11053번: 가장 긴 증가하는 부분 수열(S2)

 

 

 

 

사용한 알고리즘

2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP)

 

 

풀이

배열 arr에는 수열 A를 저장하고,
dp[i]에는 dp[i]로 끝나는 증가 부분 수열 중 합이 가장 큰 것의 값을 담아줄 것이다.

arr[i]보다 앞에 있는 수들 중 크기가 arr[i]미만인 수들 중에
(MAX dp[j])+arr[i]이 dp[i]이다.

 

 

소스코드

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

int arr[1001]; //수열A저장
int dp[1001]; //dp[i]는 dp[i]로 끝나는 합이 가장 큰 증가 부분 수열

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,ans; cin>>n;
    for(int i=0; i<n; i++) cin>>arr[i];

    dp[0]=arr[0];
    ans=dp[0];
    for(int i=1; i<n; i++){
        int sumMAX=0;
        for(int j=0; j<i; j++){
            if(arr[j]<arr[i]) sumMAX=max(sumMAX,dp[j]);
        }
        dp[i]=sumMAX+arr[i];
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}