[C++/Python] 백준 11055 - 가장 큰 증가하는 부분 수열

문제 링크

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

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

 

현재의 값이 이전의 값보다 크면 증가 부분 수열이므로 현재 위치 까지의 모든 증가 부분 수열을 배열 dp에 저장해놓고 배열 중 최대값을 구하면 됩니다. 

 

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	const int MAX = 1001;
	int num[MAX];
	int dp[MAX];
	int main(){
	fastio;
	int n;
	int max_num = 0;
	cin >> n;
	for(int i=1;i<=n;i++)
	cin >> num[i];
	for(int i=1;i<=n;i++){
	dp[i] = num[i];
	for(int j=1;j<i;j++){
	if(num[i] > num[j]){
	dp[i] = max(dp[i], dp[j] + num[i]);
	}
	}
	max_num = max(max_num,dp[i]);
	}
	cout << max_num << endl;
	return 0;
	}

view raw 11055.cpp hosted with ❤ by GitHub

	n = int(input())
	num = list(map(int, input().split()))
	dp = [0 for i in range(n)]
	for i in range(n):
	dp[i] = num[i]
	for j in range(i):
	if num[i] > num[j]:
	dp[i] = max(dp[i], dp[j] + num[i])
	print(max(dp))

view raw 11055.py hosted with ❤ by GitHub