[C/C++] BOJ 11722 :: 가장 긴 감소하는 부분 수열

BOJ 11722 :: 가장 긴 감소하는 부분 수열

문제 링크 : https://www.acmicpc.net/problem/11722

나의 풀이

1. 가장 긴 감소하는 길이를 저장할 lds 배열을 만든다.

2. 기준 idx까지 앞 쪽의 원소들을 탐색하면서 감소하는 부분 수열이 될 경우, 기준 idx의 lds를 갱신한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11722/BOJ_11722.cpp

// 백준알고리즘 11722번 :: 가장 긴 감소하는 부분 수열
#include<iostream>
using namespace std;
#define max(a,b) (a > b) ? a: b
int N;
int arr[1001];
int lds[1001];
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++)
        cin >> arr[i];
 
    for (int i = 0; i < N; i++)
    {
        lds[i] = 1;
        for (int j = 0; j < i; j++)
        {
            // 앞의 값이 큰 값이면, 길이 갱신.
            if (arr[j] > arr[i]) lds[i] = max(lds[i], lds[j] + 1);
        }
    }
 
    int ans = lds[0];
    for (int i = 1; i < N; i++)
        if (ans < lds[i]) ans = lds[i];
 
    cout << ans;
 
    return 0;
}