BOJ : 11055 가장 큰 증가 부분 수열

 

---

[BOJ 11055(S2) 리뷰]

먼저 이 문제를 풀기전에 LIS알고리즘 의 개념에 대해 알고 있어야 한다.

동적계획법을 통해 문제를 해결 할 수 있으며 기존에 크기에 대하여 계산하던 것을 합에 대하여 계산하도록만 바꾸어주면 된다.

---

#include <bits/stdc++.h>
using namespace std;

int arr[1001];
int dp[1001];

int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		dp[i] = arr[i];
	}

	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		int temp=0;
		for (int j = 0; j < i; j++)
		{
			if (arr[i] > arr[j])
			{
				temp = max(temp, dp[i] + dp[j]);
			}
		}
		dp[i] = max(dp[i], temp);
		ans = max(ans, dp[i]);
	}

	cout << ans;

	

}