[백준] 11055번*

💻 C++ 기반

가장 큰 증가 부분 수열
https://www.acmicpc.net/problem/11055

1. 테이블 정의하기
   dp[i] : i번째 수를 선택할 때의 합의 최댓값
2. 점화식 찾기

• 단순히 i-1번째 수만 가지고 비교하면 빠뜨리는 경우의 수가 많음
• 0부터 i-1번째 수까지 다 돌면서 수의 크기 비교 & dp 값 비교 필요

3. 초기값 정하기
   dp[0] = 0
   (만약 dp[1]로 초기값을 정해버리면, 수열의 첫 번째 수를 선택하지 않는 경우를 고려하지 못할수도?)

#include <cstdio>
#include <algorithm>

#define MAX_N 1001

using namespace std;

int A[MAX_N];
int dp[MAX_N];

int main()
{
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &A[i]);
        dp[i] = A[i];
    }

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

    printf("%d", *max_element(dp, dp + N + 1));
    return 0;
}

max_element(), min_element()
: [forward, last) 범위 내 최대값, 최소값을 리턴

#include <algorithm>
vector<int> v;
*max_element(v.begin(), v.end());
*min_element(v.begin(), v.end());