[BOJ][Python][실2][11055] 가장 큰 증가하는 부분 수열

문제 링크

문제링크

첫 번째 풀이

dp[i] : arr[i]를 가장 큰 수로 가지는 가장 긴 감소하는 부분 수열의 길이

LIS는 $O(n^2)$입니다.

정답 코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
import copy

# sys.stdin = open("input.txt", "r")

n = int(input())
# R, C, K = 1, n, 1
dp = [0] * n
# dp = [[0] * C for _ in range(R)]
# dp = [[[0] * K for _ in range(C)] for _ in range(R)]
# MOD = 1000000000
arr = list(map(int, sys.stdin.readline().split()))
dp[0] = arr[0]
for i in range(1, n):
    dp[i] = arr[i]
    for j in range(0, i):
        if arr[j] < arr[i] and dp[j] + arr[i] > dp[i]:
            dp[i] = dp[j] + arr[i]

print(max(dp))

Success Notice: 수고하셨습니다.