11055 가장 큰 증가 부분 수열

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MAX 1000
// 11055

int main(){
	int n;
	
	cin >> n;
	cin.ignore();
	
	vector<int> vec(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> vec[i];
	}
	
	vector<int> mem(n + 1, 0); // 해당 숫자에서의 최대 증가 배열 합을 저장 
	for(int i = 1; i <= n; i++){
		int maxMem = -1;
		for(int j = 1; j < i; j++){
			if(vec[j] >= vec[i]) continue;
			if(maxMem < mem[j]) {maxMem = mem[j];}
		}
		if(maxMem != -1) mem[i] = maxMem + vec[i];
		else mem[i] = vec[i];
	}
	
	int res = -1;
	for(int i = 1; i <= n; i++){
		if(res < mem[i]) res = mem[i];
	}
	
	cout << res << endl;

}

 

해설

11053 번 문제와 동일하다. 단지 길이를 위해 1 만을 더해주느냐. 혹은 최대 합을 구하기 위해서 해당 index 의 값을 더해주느냐의 차이 만 있었다.