백준 11055

백준 11055

n개의 수열이 주어졌을 때, 증가하는 부분 수열 중 가장 길이가 긴 수열의 길이를 구하는 문제이다.

dp[i]는 i번째 인덱스 수를 포함하고, 그 수가 최대값인 증가하는 부분 수열 중에서 최대 길이이다.

if(arr[i]>arr[j]) //증가하는 수열을 만족
	dp[i]=max(dp[i],dp[j]+1)

증가하는 수열을 만족하면 길이를 하나씩 더해가는 식이다.

#include<bits/stdc++.h>
using namespace std;
int n;
int arr[1001]; int dp[1001];
int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[i] = arr[i];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + arr[i]);
		}
	}

	sort(dp, dp + n);

	cout << dp[n - 1] << '\n';

}