https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
Best Time to Buy and Sell Stock - LeetCode
Best Time to Buy and Sell Stock - 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
leetcode.com
전형적인 dp문제다.
naive하게 생각하면 O(N^2)이지만
우리가 관심있게 생각하는건 어떤 price와 과거 price 차의 최대값이다.
그러니까 과거 price는 최소값만 가지고 있으면 된다.
그러면 필요없는 계산을 줄이고 O(N)으로 풀 수 있다.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
answer = 0
minval = prices[0]
for price in prices:
answer = max(answer, price - minval)
minval = min(minval, price)
return answer
'코딩 테스트 및 알고리즘 > leetcode for google' 카테고리의 다른 글
| leetcode hard : Contains Duplicate III (1) | 2023.01.21 |
|---|---|
| leetcode hard : Shortest Palindrome (0) | 2023.01.21 |
| leetcode hard : Word Search II (0) | 2023.01.18 |
| leetcode hard : Dungeon Game (0) | 2023.01.18 |
| leetcode hard : Maximum Gap (2) | 2023.01.18 |