알고리즘/알고리즘 문제 복기
LeetCode - 121. Best Time to Buy and Sell Stock
내일도무사히
2021. 2. 16. 22:49
leetcode.com/problems/best-time-to-buy-and-sell-stock/
Best Time to Buy and Sell Stock - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
배열문제이고, 최댓값을 구하는 문제이므로 DP를 활용해서 풀어보기로 했다.
state인 dp[x]는 x인덱스의 날에 팔았을 때의 PROFIT의 최댓값 이라고 정의를 했다.
PROFIT의 최댓값이 되려면, 이전에 stock을 산 값이 최솟값이여야
Profit 즉, 판 값 - 산 값이 최댓값이 되기 때문에
dp[i] = nums[i] - min_value라고 정의했다.
코드는 다음과 같이 짰다.
Answer
