백준 c++ 11053 가장 긴 증가하는 부분 수열

11053 가장 긴 증가하는 부분 수열

문제풀이

#include <iostream>
#include <algorithm>
using namespace std;
void fast_io(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int arr[1001], dp[1001], a;
int main()
{
    fast_io();
    cin >> a;
    for (int i = 0; i < a; i++)
        cin >> arr[i];
    for (int i = 0; i < a; i++)
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j] + 1);
    }

    cout << *max_element(dp, dp + a);
}

lis알고리즘을 쓸 일이 생겨서 풀어봤다.
Longest Increasing Subsequence 는 최장 증가 부분 수열이라는 알고리즘이다.
계속 틀렸는데 어이없는 실수를 했다.
i보다 작은 원소를 찾고, 작은원소의 dp값 + 1과 i의 dp값을 비교한뒤 최장길이인 dp값을 보여준다.