11055) 가장 큰 증가 부분 수열 c++

문제 ) www.acmicpc.net/problem/11055

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

 

풀이 ) 만약 아직 11053번 문제를 풀지 않았다면, 먼저 풀고 오길 바란다.

1. dp[i] = A[i] 값을 대입한다. 

2. A배열의 맨처음 수부터 계속해서 비교하기 위해서 j의 범위를 i까지 만으로 지정

3. 현재 비교할 수열의 값이 바로 직전의 값보다 클 경우

4. 증가하는 부분 수열의 길이를 하나 증가해야하므로 dp[i]값을 바꿔준다.

5. sum 변수에는 합이 가장 큰 증가 부분 수열 값만 넣어서 반환한다.

 

 

코드 ) 

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

int N, sum;
int A[1001];
int dp[1001];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for(int i=0; i<N; i++)
		cin >> A[i];
	
	for(int i=0; i<N; i++) {
		dp[i] = A[i];					// 1
		
		for(int j=0; j<i; j++) {			// 2
			if( A[i] > A[j] ) {			// 3
				dp[i] = max(dp[i], dp[j]+A[i]);	// 4
			}
		}
		sum = max(sum, dp[i]);				// 5
	}
	cout << sum;
}