[ 백준 / Python ] #25214 크림파스타

문제

 

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

25214번: 크림 파스타

---

Algorithm

1 ≤ i ≤ j ≤ len(A)을 만족하는  A[j] - A[i]의 최댓값을 구하는 문제이다.

dp배열을 만들어주고, 각 배열의 첫번째 원소는 i-1까지의 최댓값과 A[i] 와 dp[i-1]까지의 최솟값의 차이중 최댓값을 취한다.각 배열의 두번째 원소는 dp[i-1] 과 A[i]의 최솟값을 취해주고 dp배열을 점점 확장해나가면 된다.

최종 출력은 첫번째원소를 출력해주면 된다.

---

 

 

Code

input = __import__('sys').stdin.readline

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

dp = [[0,1000000000]]

for i in range(1,n+1):
    dp.append([max(dp[i-1][0] , arr[i-1] - dp[i-1][1]),min(dp[i-1][1],arr[i-1])])

for i in range(1,n+1):
    print(dp[i][0], end = ' ')