Memo

• 기본적으로 루프를 0 부터 N - 1까지 돌면서 확인합니다.
• cal_max함수는 첫 번째 인자로 함수 밖에서 비교중인 인덱스, 두 번째 인자로 함수 밖에서 비교중인 인덱스에 들어있는 값을 받습니다.
• cal_max 함수 내에서 첫 번째 인덱스 보다 큰 값들을 비교합니다.
• 비교하는 과정에서 첫 번째 인자의 위치에 있는 값보다 크다면 함수를 재귀적으로 호출하여 그 인덱스에 들어있는 dp값을 바꿔줍니다.
• 다음 루프에서 해당 인덱스에 dp값이 들어있다면 그것을 그대로 사용합니다.

Code

제출 날짜

2021/03/23

메모리

2016 KB

시간

0 ms

#include <iostream>
#include <vector>
#include <algorithm>

size_t N;
std::vector<int> arr;
std::vector<int> dp;
int ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> N;
	arr.resize(N);
	dp.resize(N);
	for (size_t i = 0 ; i < N ; i++)
		std::cin >> arr[i];
}

int cal_max(int p_i, int val)
{
	int max_val = 0;

	if (p_i >= static_cast<int>(N))
		return (0);
	if (dp[p_i])
		return (dp[p_i]);
	for (size_t i = p_i + 1 ; i < N ; i++)
		if (arr[p_i] < arr[i])
			max_val = std::max(max_val, cal_max(i, arr[i]));
	dp[p_i] = max_val + val;
	return (max_val + val);
}

void solve()
{
	for (size_t i = 0 ; i < N ; i++)
		ans = std::max(ans, cal_max(i, arr[i]));
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}