글 읽기 - 제 코드의 시간복잡도는 어떻게 구하는건가요?

dh0450 2년 전 0

테스트 몇개 해보니까

1, 2, 3, 4 ... Len(LIS)

이렇게 나오는데 왜그런지 모르겠네요.

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0); setvbuf(stdout, nullptr, _IOFBF, BUFSIZ);
#pragma warning(disable:4996)
#include <unordered_set>

#define MAX_LINE 1001
int lis[MAX_LINE], cnt = 0;
int inputs[MAX_LINE], indices[MAX_LINE];


unordered_map<int, unordered_map<int, int>> dp; 
int DFS(int p, int idx, int sum = 0)
{
	if (p == -1) return sum;

	if (dp[p].find(idx) != dp[p].end())
		return dp[p][idx] + sum;

	int f, fi;
	for(fi = idx; fi >= 0; fi--)
		if (indices[fi] == p)
		{
			f = inputs[fi];
			break;
		}

	dp[p][idx] = max(DFS(p - 1, fi - 1, sum + f), DFS(p - 1, idx, sum)) - sum;

	return dp[p][idx] + sum;
}

int main()
{
	int n;
	cin >> n;

	// LIS 업데이트
	for (int i = 0; i < n; i++) cin >> inputs[i];
	for (int i = 0; i < n; i++)
	{
		int *p;
		p = lower_bound(lis, lis + cnt, inputs[i], [](int a, int b) { return a > b; });
		*p = inputs[i];
		if (p - lis == cnt) cnt++;
		indices[i] = p - lis;
	}

	// 값 추적해서 최댓값 구하기
	cout << DFS(cnt-1, n-1);
}