백준 11055 가장 큰 증가 부분 수열(C++)

https://tigerfrom2.tistory.com/33

백준 11053 가장 긴 증가하는 수열(C++)

 수열 시리즈 문제이다. 이번에는 합을 DP에 담아서 갱신하면 된다.

코드가 매우 유사하므로 먼저 위 문제를 풀어보는게 좋다.

 

1 3 2 4 를 예로 들어보자. 모든 DP[N] = N 으로 갱신되어있다. 왜? 본인은 언제나 합에 포함되니까

1. 1이 들어오면 -> DP[1] = 1

2. 3이 들어오면 -> DP[3] = max(DP[1] + DP[3] , DP[3])

3. 2가 들어오면 -> DP[2] = max(DP[1] + DP[2] , DP[2]) -> 3은? 2보다 크기 때문에 증가 수열로 치지않는다.

4. 4가 들어오면 -> DP[4] = max(DP[1] + DP[4] , DP[4] -> DP[4] = max(DP[3] + DP[4] , DP[4]) 

두번 갱신을 확인한다. 왜냐면 4보다 작은 값이 두개이기 때문에 이 두수열이 증가할 수 있는 여지가 있다. 

 

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

int main() {
	int n, m;
	int DP[1001] = { 0, };
	vector<int> vec;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> m;
		vec.push_back(m);
		DP[m] = m;
	}

	int answer = 0;
	
	for (int i = 0; i < vec.size(); i++) {
		int sum = 0;
		for (int j = 0; j < i; j++) {
			if (vec[i] > vec[j]) {
				DP[vec[i]] = max(DP[vec[j]] + vec[i], DP[vec[i]]);
			}
		}
		answer = max(answer, DP[vec[i]]);
	}

	cout << answer << endl;
}