1. 문제 설명

주식

2. 문제 분석

그리디 알고리즘. 로콜 최댓값을 어떻게 구하는지가 관건인 문제.

• 처음에는 인덱스를 앞에서 체크하면서 로컬 최댓값을 max(prices[idx:])로 구했는데, 아니나 다를까 시간 초과. max 연산을 할 필요 없이 뒤에서부터 기록할 때 효율적으로 풀 수 있었다.

3. 나의 풀이

import sys
t = int(input())

for _ in range(t):
    n = int(input())
    prices = list(map(int, sys.stdin.readline().rstrip().split()))
    prices.reverse()

    local_max = prices[0]
    # 현재 인덱스와 비교하는 로컬 최댓값은 0번의 가격
    plus = 0

    for i in range(n):
        if local_max == prices[i]: continue
        # 같다면 계산하는 의미 X
        elif local_max > prices[i]: plus += local_max - prices[i]
        # 이익을 낼 수 있다면 계산
        else: local_max = prices[i]
        # 로컬 최댓값을 변경
    print(plus)