[백준] 11055번. 가장 큰 증가하는 부분 수열 (C++)

문제

https://www.acmicpc.net/problem/11055

풀이

[DP, LIS알고리즘]

저번에 푼문제랑 비슷해서 후딱풀었다

 

숫자들을 차례대로 확인한다

지금 확인할 숫자가 n번째 숫자라고 하자

0~n-1번째 숫자들 중 n번째 숫자보다 작은 숫자를 m이라고 하자

"dp[m]+n번째 숫자"가 "dp[n]"보다 크면 dp를 갱신한다.

 

dp중에 제일 큰 값이 정답!

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int N; cin >> N;
	int maxN=0;
	vector<int>number(N);
	vector<int>dp(N);
	for (int i = 0; i < N; i++)
	{
		cin >> number[i];
		dp[i] = number[i];
		for (int j = 0; j < i; j++)
		{
			if(number[i]>number[j])
			{
				dp[i] = max(dp[j] + number[i], dp[i]);
			}
			if (dp[i] > maxN) { maxN = dp[i]; }
		}
	}

	cout << *max_element(dp.begin(), dp.end());
}

 

유사한 문제

https://yun000.tistory.com/163

[백준] 11722번. 가장 긴 감소하는 부분 수열 (C++)