11053_가장 긴 증가하는 부분 수열

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

#include<iostream>

using namespace std;

int main() {
	int input,i,j;
	int max,fin=0;
	cin >> input;
	int *num = new int[input];
	int *dp = new int[input];
	for (i = 0; i < input; i++) {
		cin >> num[i];
	}
	//그러니까 이거는 먼저 1개를 고정해놓고 그 고정된수가 가장 크다고 가정하고 
	//처음부터 고정된수와 비교한다 
	//비교해서 움직이는수가 고정된수보다 작으면 증가하는 수열을 이룰수있으므로
	//그 수가있는 인덱스의 디피값과 비교하여 지금까지 움직이는 수열의 dp값중 최대값을 골라낸다.
	//그리고 그수의 최대값에 +1을한게 고정된수의 dp값이 된다.
	for (i = 0; i < input; i++) {
		max = 0;
		for (j = 0; j < i; j++) {
			if (num[j] < num[i]) {//맨뒤의 수보다 작으면 (처음부터 선택되는 수가)
				if (max < dp[j]) {
					max = dp[j];
				}
			}
		}
		dp[i] = max + 1;
		if (fin < dp[i])
			fin = dp[i];
	}
	cout << fin;
	

	return 0;
}