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

 

 

 

 

 

 

[가장 긴 증가하는 부분수열] 문제와 매우 비슷한(거의 같음) 유형이다.

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

 

가장 긴 증가하는 부분수열을 찾을 때에는 앞의 원소보다 지금원소가 크다면 길이를 1씩 더해가면서 풀었다면,

가장 큰 증가 부분수열을 찾을 때에는 합을 구해가면서 찾는다.

 

 

 

 

 

풀이 예시

{1, 10, 2, 5, 20}이런 수열이 있을 때,

 

1에서 출발한다. 자기자신이므로 합은 1이다.

--> dp[1] = 1

 

10에 도착했다. 10>1을 만족하므로 합은 11이다.

--> dp[2] = 11

 

2에 도착했다. 2와 앞의 원소를 하나씩다 비교하여 최댓값을 골라낸다.

• 2>1을 만족하므로 합은 dp[1]+2 = 3

--> dp[3] = 3

 

5에 도착했다. 5와 앞의 원소를 하나씩 다 비교하여 최댓값을 골라낸다.

• 5>1을 만족하므로 합은 dp[1]+5 = 6
• 5>2을 만족하므로 합은 dp[2]+5 = 8

둘중 큰 값은 8이다.

--> dp[4] = 8

 

20에 도착했다. 20과 앞의 원소를 하나씩 다 비교하여 최댓값을 골라낸다.

• 20>1을 만족하므로 합은 dp[1]+20 = 21
• 20>10을 만족하므로 합은 dp[2]+20 = 31
• 20>2을 만족하므로 합은 dp[3]+20 = 23
• 20>5를 만족하므로 합은 dp[4]+20 = 28

넷중 큰 값은 31이다.

--> dp[5] = 31

 

 

dp의 값을 나열해보면 다음과 같다.

1, 11, 3, 8, 31

따라서 가장 큰 값을 골라내면 답은 31이다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>
 
using namespace std;
 
const int MAX = 1001;
int n;
int dp[MAX];
int arr[MAX];
int maxhap = 0;
 
int main(void)
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        dp[i] = arr[i];
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (arr[i] > arr[j])
            {
                dp[i] = max(dp[i], dp[j] + arr[i]);
            }
        }
        maxhap = max(maxhap, dp[i]);
    }
    cout << maxhap;
    
    return 0;
}