# 최대 수익 문제를 푸는 두 알고리즘의 계산 속도 비교하기

# 최대 수익 문제를 O(n * n)과 O(n)으로 푸는 알고리즘을 각각 수행하여

# 걸린 시간을 출력/비교함

import time     # 시간 측정을 위한 time 모듈

import random   # 테스트 주가 생성을 위한 random 모듈

# 최대 수익: 느린 O(n * n) 알고리즘

def max_profit_slow(prices):

    n = len(prices)

    max_profit = 0

    for i in range(0, n - 1):

        for j in range(i + 1, n):

            profit = prices[j] - prices[i]

            if profit > max_profit:

                max_profit = profit

    return max_profit

# 최대 수익: 빠른 O(n) 알고리즘

def max_profit_fast(prices):

    n = len(prices)

    max_profit = 0

    min_price = prices[0]

    for i in range(1, n):

        profit = prices[i] - min_price

        if profit > max_profit:

            max_profit = profit

        if prices[i] < min_price:

            min_price = prices[i]

    return max_profit

def test(n):