DP 동적프로그래밍 | BOJ 백준 11053번 가장 긴 증가하는 부분 수열 | Python


created_at : 02 April 2024 - 2 mins read time
Tags: DP 동적프로그래밍

Table of Contents


BOJ 백준 11053번 가장 긴 증가하는 부분 수열 | Python

📌 백준 11053번 문제 바로가기


🔎 문제 설명

🩶 실버 2

- 난이도 ★★☆☆
- DP 동적프로그래밍

이 문제는 백준 11053번을 살짝 꼰 문제라고 할 수 있다.

dp for문에 증가하는 부분 수열의 합을 저장하는 것이 포인트!
이중 for문을 이용해서

1) 증가하는 부분수열이라면, 이전까지 더한 값과 현재까지 더한 값 비교 2) 증가하지 않는다면, 이전까지 더한 값과 현재 값 비교해서 대치

를 지정해주었다.



💻 내 코드

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))

dp = [0]*(1001)
dp[0] = A[0]

for i in range(1,n):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[j]+A[i],dp[i])
        else:
            dp[i] = max(dp[i], A[i])

print(max(dp))




 

💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).