[algo] DP : Stock maximize

hacker rank

Stock Maximize | HackerRank

#!/bin/python

import math
import os
import random
import re
import sys


# Complete the stockmax function below.
def stockmax(prices):
    max = 0
    profit = 0
    for i in reversed(range(0, len(prices))):
        if max < prices[i]:
            max = prices[i]
        profit += max - prices[i]

    return profit


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(raw_input())

    for t_itr in xrange(t):
        n = int(raw_input())

        prices = map(int, raw_input().rstrip().split())

        result = stockmax(prices)

        fptr.write(str(result) + '\n')

    fptr.close()

• i번째 가격과 그 이후의 날들 중에서 max 값을 찾는 방식은 O (N²)
• 거꾸로 부터 읽어들여서 max 값을 갱신하는 식으로 O(N)으로 해결 가능