시간순으로 작성된 배열의 숫자들의 차이값 중 가장 큰 값을 구하라.
단, 나중 값에서 먼저 작성된 값을 빼야한다.
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

22-05-30

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        
        buy = 10000
        profit = 0
        n = len(prices)
        for i in range(0,n,2):
            if i == n-1:
                profit = max(profit,prices[i]-buy)
            else:
                j = i + 1
                profit = max(profit,prices[j]-prices[i],prices[j]-buy,prices[i]-buy)
                buy = min(buy,prices[i],prices[j])
            print(profit)
        return profit

인덱스 두 개를 사용하여 시간 복잡도를 줄이고자 하였다.
1475ms로, 아쉬운 성능.

Next what to do.
1. 70ms 이하로 줄일 수 있다!

24-10-20

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        
        n = len(prices)

        if n == 1:
            return 0

        buy, profit = 10**(4), 0
        for i in range(n-1):
            buy = min(buy, prices[i])
            profit = max(profit, prices[i+1]-buy)

        return profit

O(n)으로 해결함
run time - 114ms

이전 코드 보완 사항

• n == 1 예외 처리 진행
• min & max 사용 간소화

Run time을 더 줄이고 싶다면?

• len(prices)를 사용하지 않고 진행하면 시간이 더 줄 수 있음