https://www.acmicpc.net/problem/11501
시간 2초, 메모리 128MB
input :
- 테스트케이스 수를 나타내는 자연수 T
- N(2 ≤ N ≤ 1,000,000)
- 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
output :
- 최대 이익을 나타내는 정수 하나를 출력
조건 :
- 주식 하나를 산다.
- 원하는 만큼 가지고 있는 주식을 판다.
- 아무것도 안한다.
앞에서 부터 생각하는 것이 패착이었다.
앞에서 부터 세아리려고 한다면?
현재까지 이 값보다 작은 값들을 기록해 두어야 하고 이는 메모리 초과 혹은 시간 초과를 발생시키기 쉽다.
그래서 뒤에서 부터 시작하도록 접근해야 한다.
뒤에서 부터 우린 가장 비쌌던 값을 저장해 현재의 값과 비교한 후 이 차를 기록 하면서 최대 이익을 찾으면 된다.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
max_val = data[-1]
res = 0
for j in range(len(data) - 2, -1, -1):
val = data[j]
if val > max_val:
max_val = val
else:
res += max_val - val
print(res)
