Category
알고리즘  dp

[2229] 조 짜기

by Hwang

문제

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

풀이

dp[i]는 i번째 학생까지 고려했을 때의 최대 점수 차이 합계를 의미함

import sys

N = int(sys.stdin.readline())
scores = [0] + list(map(int, sys.stdin.readline().strip().split()))
dp = [0] * (N + 1)

for i in range(1, N + 1):
    dp[i] = dp[i - 1]
    max_num = min_num = scores[i]
    for j in range(i-1, 0, -1):
        max_num = max(max_num, scores[j])
        min_num = min(min_num, scores[j])
        dp[i] = max(dp[i], dp[j - 1] + (max_num - min_num))
print(dp[i])


 Comment