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

문제

https://www.acmicpc.net/problem/11053
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

풀이

LIS를 이용한 풀이
각 idx에서 제일 길게 만들 수 있는 수열 길이를 저장한다.

입력한 수열을 탐색하면서 해당 index 이전에 나온 수들 중 현재 수 보다 작다면 그 수가 가지고 있는 길이를 모두 포함할 수 있는 것이다.🙀

현재 인덱스 i, 0~i까지 내부 반복문 인덱스 k
arr[i] < arr[k]인 것이 있을 경우, length[k] 를 업데이트한다.
업데이트는 max(l[i] , l[k]+1)

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, a[1001], l[1001], mx = -1;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        l[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (a[j] < a[i])
                l[i] = max(l[i], l[j] + 1);
        }
        mx = max(mx, l[i]);
    }
    cout << mx << "\n";
    return 0;
}