백준/11055번/가장 큰 증가하는 부분 수열/실버2

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

문제 설명

Site: Baekjoon
Number: 11055
Category: Dynamic Programming
Rank: Silver 2

주어진 수열에서 증가하는 부분 수열 중 그 합이 가장 큰 부분 수열을 찾는 문제.

2단계로 나누어 해결할 수 있다.

1. 각 요소마다 for문을 돌며 이전 요소 중 자신보다 작은 요소가 있는지 확인한다. 1.a 자신보다 작은 요소들의 dp값에서 자기 자신의 값을 더한 값 중 최댓값을 자신의 dp값에 저장 1.b 자신보다 작은 요소가 없는 경우 자기 자신의 값을 dp값에 저장

2. dp값 중 최댓값을 출력

#include <iostream>

using namespace std;

int arr[1001];
int dp[1001];

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

    int N;
    cin >> N;

    for (int i = 0; i < N; i++)
        cin >> arr[i];

    dp[0] = arr[0];
    for(int i = 1; i < N; i++)
    {
        dp[i] = arr[i];
	    for(int j = i; j > -1; j--)
	    {
            if (arr[j] < arr[i])
            {
                dp[i] = max(dp[i],dp[j] + arr[i]);
            }
	    }
    }

    int ans = 0;
    for (int i = 0; i < N; i++)
        ans = max(ans, dp[i]);

    cout << ans;

    return 0;
}