You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 105
0 <= prices[i] <= 104
먼저 이러한 문제를 해결하기 위해선 2가지 변수가 필요하다.
1. 구매 가격 변수
2. 최대 이익 변수
이제 변수를 만들었으면, 시간 순서대로(인덱스 순서대로) 진행하면서 최선의 결과를 선택하면 된다.
저점(구매 지점)을 계속 갱신 > 현재 값에서 빼기 > 최대 이익과 (현재값 - 저점) 비교해여 최대이익 갱신 순으로 진행하면 된다.
TEST CASE
[1 7 8 5] = 7
[2 7 1 8] = 7
[2 7 1 5] = 6
class Solution:
def maxProfit(self, prices: List[int]) -> int:
buy = None
profit = 0
for i in prices:
if buy is None:
buy = i
else:
if i < buy:
buy = i
else:
temp = i - buy
profit = max(temp, profit)
else:
if profit < 0:
profit = 0
return profit