7311 : 재귀 최장 증가 부분수열
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
수열이 주어질 때 최장 증가 부분수열(LIS: Longest Increasing Subsequence)의 길이를 재귀 + 메모이제이션으로 구하십시오.
각 원소 $i$에서 시작하는 LIS의 길이: $\text{LIS}(i) = 1 + \max_{j > i, A[j] > A[i]} \text{LIS}(j)$
시간 복잡도: $O(N^2)$
[제약 조건]
• 입력되는 모든 수는 정수입니다.
각 원소 $i$에서 시작하는 LIS의 길이: $\text{LIS}(i) = 1 + \max_{j > i, A[j] > A[i]} \text{LIS}(j)$
시간 복잡도: $O(N^2)$
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 수열의 크기 $N$이 주어집니다. ($1 \le N \le 1{,}000$)
둘째 줄에 $N$개의 정수가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
출력 설명
재귀와 메모이제이션을 사용하여 계산한 최장 증가 부분수열의 길이를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8
5 1 4 2 8 3 7 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
memo = {}; def lis(i): if i in memo: return memo[i]; memo[i] = 1 + max((lis(j) for j in range(i+1,n) if arr[j]>arr[i]), default=0); return memo[i]. 최종 답은 max(lis(i) for i in range(n))입니다.