[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]

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

Longest Increasing Subsequence(이하 LIS)를 이용하여 푸는 문제이다.

일단 최대한 간단하고 직관적으로 풀었다.

ary[]에는 값을 전부다 받아왔고

lis[]는 배열을 줄을 세워 줄의 길이를 넣었다. 초기값은 1로 해야한다.

output는 lis[0]로 초기화한다.

#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
int ary[1001];        //array
int lis[1001];        //LIS values
 
int main() {
    int N, input, output;
    int sum = 0;
 
    scanf("%d", &N);
 
    for (int k = 0; k < N; k++) {
        scanf("%d", &input);
        ary[k] = input;
    }
 
    for (int k = 0; k < N; k++) 
        lis[k] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < i; j++) {
            if (ary[i] > ary[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1;
            }
        }
    }
 
    output = lis[0];
    for (int k = 0; k < N; k++) {
        if (output < lis[k]) {
            output = lis[k];
        }
    }
 
    printf("%d", output);
 
    return 0;
}