[백준]Baekjoon11053(Dynamic Programming)(LIS)

문제링크 : https://www.acmicpc.net/problem/11053

LIS알고리즘이 적용되는 과정에 대한 이해가 필요하다면 :

http://dolphins-it.tistory.com/82  참조

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

int A[1001];
int memo[1001];

int main()
{
	int n; 
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &A[i]); // 주어지는 수열 A
	int max = 1; //최장 수열의 길이

	for (int i = 1; i <= n; i++) {
		memo[i] = 1; //기본적으로 가지는 부분수열의 길이인 1을 할당
		for (int j = 1; j < i; j++) { // i가 가리키는 수 앞에있는 배열을 검사
			if (A[j]<A[i] && memo[j] + 1 > memo[i]) {
				//앞에서 A[i]보다 작은것중 memo[i]보다 최장 수열의 길이가 길다면
				memo[i] = memo[j] + 1;
				//기본 수열의 길이 1에 해당 최장 수열의 길이를 더한다.
			}
		}
		if (memo[i] > max) max = memo[i];
	}
	printf("%d\n", max);
}