[LIS] (CHECK) 백준 11053 가장 긴 증가하는 부분 수열 C++

※ 문제

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

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

 

※ 풀이

- 초기화 dp[i]=1 (i=1부터 n까지)
- dp[i] := max(dp[i], dp[j]+1) (수열[i] > 수열[j]) (i=2부터 n까지, j=1부터 (i-1)까지)

∴ 1부터 n까지 dp 배열의 최댓값

#include<stdio.h>
#define max(a,b) (((a)>(b))? (a) : (b))

int main()
{
    int n, maxN = 1;
    int arr[1001], dp[1001];

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

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1);
        }
        maxN = max(maxN, dp[i]);
    }

    printf("%d", maxN);
}