백준_11055_가장 큰 증가 부분 수열

앞서 푼 다이나믹 프로그래밍(dp) 문제들과는 점화식의 로직이 살짝 달랐다.

j를 1~(i-1) 로 증가시켜가면서 d[i]값을 갱신하는 것이 핵심이었다.

 

#include <iostream>
#include <algorithm>
#define MAX 1001

using namespace std;

int N, A[MAX], d[MAX], answer;

void dp() {
	int maxD = 0;
	for (int i = 1; i <= N; i++) {
		d[i] = A[i];
		for (int j = 1; j < i; j++) {
			if (A[i] > A[j])
				d[i] = max(d[i], d[j] + A[i]);
		}
		maxD = max(maxD, d[i]);
	}
	answer = maxD;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	dp();
	cout << answer << '\n';
	return 0;
}