[C/C++ 백준 11055번] 가장 큰 증가 부분 수열 (Silver 2)

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

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

은근 까다로운 문제였다. 예전에 못 풀어서 손 놓고 있었는데, 다시 풀어보니 풀리더라.

 

일단 i까지 가장 큰 증가 부분 수열의 합을 저장하는 ans를 만들고, dp[i] 배열은 i번째 원소를 포함하는 가장 큰 부분 증가 수열이다. 매 원소(A[i])를 입력받으면서 ans와 dp[i]를 비교하면 쉽게 해결된다.

---

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int N, A[1001]={}, dp[1001]={}, maxi, ans=-1;
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		scanf(" %d",&A[i]);
		maxi=-1;
		for(int j=0; j<i; j++){
			if(A[j]<A[i])
				maxi=max(maxi, dp[j]+A[i]);
		}
		maxi=max(maxi, A[i]);
		dp[i]=maxi;
		ans=max(ans, dp[i]);
	}
	printf("%d",ans);
}

---