[알고리즘/DP] 백준 11055번: 가장 큰 증가 부분 수열 - C++

www.acmicpc.net/problem/11055

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

다이나믹 프로그래밍(DP)을 이용하였다

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

int a[1000], d[1000];

int main() {
	int n, ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];

	for (int i = 0; i < n; i++) {
		d[i] = a[i];
		for (int j = 0; j < i; j++) {
			if(a[i] > a[j])
				d[i] = max(d[i], d[j] + a[i]);
		}
	}
	for (int i = 0; i < n; i++)
		ans = max(ans, d[i]);
	cout << ans;
}

 

github.com/waves123/11055/blob/master/11055/11055.cpp

waves123/11055

 

다이나믹 프로그래밍 문제

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 1912번: 연속합 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 11055번: 가장 큰 증가 부분 수열 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 11052번: 카드 구매하기 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 9095번: 1,2,3 더하기 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 11726번: 2xn 타일링 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 1463번: 1로 만들기 - C++