[BOJ 11501] 주식

쌀때 사서 최댓값에 판다

최댓값 $M_1$을 찾고, 구간 [...$M_1$]에서 수익을 계산한다. 그리고 다시 남은 구간에서 이 작업을 반복한다. 이러면 $O(N^2)$이라 시간초과가 발생한다.

각 구간의 최댓값을 $M_1, M_2, ...M_n$이라 하면
[....$M_1$], [....$M_2$], ..., [...$M_n$] 이렇게 $n$개의 구간이 생긴다. 따라서 배열의 뒤에서부터 최댓값 $M_k$을 찾고, $M_k$보다 큰 값이 생기면 그 값을 $M_{k-1}$로 하여 구간을 분리한다.

3번째 예제(1 1 3 1 2)로 설명해보면
뒤에서부터 배열을 순회하여 [2, 1] 구간을 찾고, 3은 현재구간의 최댓값인 2보다 크므로 구간을 분리한다. 따라서 생기는 구간은
[2 1], [3 1 1]이 된다.

[1 2 5 4 3 7 6 5 9 8]의 경우는
[8], [9 5 6 7 3 4 5 2 1]이므로 39가 답이다. (첫번째 구간인 [8]에서는 주식을 사거나 팔지 않고 아무 행동도 하지 않으므로 수익이 0이다)

import sys
#sys.stdin = open('input.txt', 'r')
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    prices = list(map(int, input().split()))
    profit = 0
    buys = []
    for price in prices[::-1]:
        if buys and buys[0] < price:
            for buy in buys:
                profit += buys[0] - buy
            buys = []
        buys.append(price)
    if buys:
        for buy in buys:
            profit += buys[0] - buy
    print(profit)