배열 최대, 최소 탐색 (one-way search)

                                    🤔 단순히 O(n²)으로  풀 수 있다.

>>> 하지만 입력값이 10,000이라서 사용하기에는 무리다.

❓❔ 더 효율적인 방법은 무엇인가...

                                    class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        profit = -99
        for i in range(len(prices)):
            buy = prices[i]
            for j in range(i + 1, len(prices)):
                sell = prices[j]

                if sell - buy >= 0:
                    profit = max(profit, sell - buy)

        if profit < 0:
            profit = 0
        return profit

                                    # 정렬 ?
[7,1,5,3,6,4] 최소 값 idx 순서대로 정렬

# idx
[1, 3, 5, 2, 4, 0]
이렇게 되면 1에는 최소 0에는 최대가 들어있다.

>>> 문제 특성상 최소 값 보다 작은 최대 값 idx를 고를 수 없다.
>>> 그럼 이번 문제는 1, 4가 선택되고 결과는 최소 idx = 1, 최대 idx = 4가 되어 정답이 5이다.

❓🤔 O(nlogn)인가?
>>> case 1 [5, 4, 3, 2, 1] 정렬되어 있다고 하면, 최솟값 5를 고르고 끝에서 전체 탐색
그 다음 최솟값 4를 고르고 끝에서 전체 탐색이라서 최종 탐색 시간은 n(n-1)이 된다.

>>> 여전히 최악의 경우 시간 복잡도는 O(n²)을 벗어나지 못한다...

❓ 해당 케이스만 예외적으로 처리하면?
>>> 생각해보면 해당 케이스는 문제에서 요구되는 -1이 return되는 경우다.
>>> 이 경우는 항상 이전 날의 값이 다음날 값 보다 작다는 특징을 가지고 있다.
>>> 이를 사전에 미리 체크해서 따로 처리한다면 O(n) 속도로 처리가 가능하다.

🤔 그럼에도 벗어날 수 없다.
[max, max-1, max -2, max -3 ....., ,..... min] 형태에서 중간 어떤 부분에서 두 값이 바뀌는
경우가 존재한다.

모든 배열은 항상 앞의 idx가 크다가, 어느 한 순간 앞이 뒤보다 작은 경우가 생길 수 있다.
[...  2, 3  ....]
하지만 이 경우에도 앞에서 뒤로 계속해서 탐색이 이루어져야 하기 때문에 여전히 O(n²)이다.

>>> 그럼에도 여전히 O(n²)

                                    0. min_price = 가격의 최댓값으로 설정, profit = -1
1. 배열 순회를 시작한다.
>>> price가 min_price보다 작다 -> min_price를 갱신한다.
>>> 크다 profit을 갱신한다.

                                    class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        min_price = 10001
        profit = -1
        for i in range(len(prices)):
            if prices[i] < min_price:
                min_price = prices[i]
                continue
            else:
                profit = max(profit, prices[i] - min_price)

        if profit < 0:
            profit = 0
        return profit

                                    class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        price_min = prices[0]
        price_max = 0
        profit = 0
        for price in prices:
            if price < price_min:
                price_min = price
                price_max = price
            elif price > price_max:
                price_max = price
                profit = max(price_max - price_min, profit)
        return profit