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

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

​

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

11053번: 가장 긴 증가하는 부분 수열

11053번 제출 맞은 사람 숏코딩 재채점/수정 채점 현황 강의 가장 긴 증가하는 부분 수열 분류 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 45454 17145 11564 37.071% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = { 10 , 20 , 10, 30 , 20, 50 } 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기...

www.acmicpc.net

​

lis O(n^2)

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int a;
	cin >> a;
	int arr[1001];
	for (int i = 1; i <= a; i++) {
		cin >> arr[i];
	}
	int dp[1001];
	int length = 0;
	for (int i = 1; i <= a; i++) {
		dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (arr[j] < arr[i] && dp[i] < dp[j]+1) {
				dp[i]=dp[j]+1;
			}
		}
		if (length < dp[i])length = dp[i];
	}
	cout << length;
}