11055번 가장 큰 증가 부분 수열

문제 링크

가장 큰 증가 부분 수열

문제 풀이

배열의 0 번 인덱스에 0을 저장시킨 후, 0 번 인덱스에서 시작하고 현재 인덱스에서부터 끝까지 for문을 돌면서 현재 배열의 값보다 큰 값이 나올때마다 재귀 호출을 해준다. 그리고 마지막 인덱스에 도착할때를 기저 사례로 둔다.

구현

#include <iostream> 
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int N, A[1001];
int cache[1001];

int solve(int index) {
    if (index == N + 1) return 0;

    int& ret = cache[index];
    if (ret != -1) return ret;
    
    ret = 0;
    for (int i = index + 1; i <= N; ++i) {
        if(A[index] < A[i])
            ret = max(ret, solve(i) + A[i]);
    }
    return ret;
}

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

    cin >> N;
    for (int i = 1; i <= N; ++i)
        cin >> A[i];
    memset(cache, -1, sizeof(cache));

    cout << solve(0);
    return 0;
}