[Algorithm] BOJ 11053번

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
int *arr;
int *memo;
int lss(int size)
{
    int min_or_max;
    int cnt = 0;
    int answer = 1;
    for (int i = 0; i < size; i++)
    {

        memo[i] = 1;
        for (int j = 0; j < i; j++)
        {
            int mid_result = memo[j];
            if (arr[i] > arr[j])
                mid_result += 1;
            else
                continue;
            if (mid_result > memo[i])
                memo[i] = mid_result;
        }
        if (memo[i] > answer)
            answer = memo[i];
    }

    return answer;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int size;
    cin >> size;
    arr = new int[size];
    memo = new int[size];
    for (int i = 0; i < size; i++)
        cin >> arr[i];

    int result;
    result = lss(size);
    cout << result;
}

 

시간복잡도 O(N^2)의 방법이다.