[백준 11053] 가장긴증가하는부분수열

문제

https://www.acmicpc.net/problem/11053
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

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

입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

아이디어

뒤에서부터 한 원소마다 그 원소를 시작으로 한 LIS의 길이(lis[i]...lis[n-1])를 저장해두고 앞 원소의 lis[i-1]를 구할 땐 뒤 lis[i]..lis[n-1]중에서 이 원소를 앞머리로 붙일 수 있는 LIS가 있을지 검사하며 최대값을 찾는다.
예에오늘 생각해도 같은아이디어
아참, 전체 순열에서 가장 긴 lis 길이는 시작점이 어디가 될지 모르므로 마지막에 쭉 돌며 최댓값 찾는다.(lis 배열채우는 과정의 2번째 for문도 비슷한 의미로 linear)

코드

#include<iostream>
#include<algorithm>
using namespace std;
//lis
int main() {
	int n;
	cin >> n;
	int *a = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	int *b = new int[n];
	//뒤에서부터 작은 LIS 계산

	b[n - 1] = 1;
	
	for (int i = n - 1; i >= 0; i--) {
		int diff = n - 1 - i;//i== n-2면 diff==1

		b[i] = 1;//나 자신이 b[i]인 경우
		for (int j = 1; j <= diff; j++) {
			//b[i+j]중 나랑 매치되는 것 중 가장 큰 것 찾기
			//만약 못찾는다면 나 자신이 b[i]가 된다
			if (a[i + j] > a[i]) {
				b[i] = max(b[i], b[i + j] + 1);
			}
		}
	}

	/*
	for (int i = n - 1; i >= 0; i--) {
		cout << "i는 " << i << " " << b[i] << endl;
	}
	*/
	//b[0]가 답이 아니다!!!!

	int answer = 1;
	for (int i = 0; i < n; i++) {
		answer = max(answer, b[i]);
	}
	cout << answer << endl;
	delete[] a;
	delete[] b;
}