LeetCode - 121. Best Time to Buy and Sell Stock

leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

 

 

 

배열문제이고, 최댓값을 구하는 문제이므로 DP를 활용해서 풀어보기로 했다.

state인 dp[x]는 x인덱스의 날에 팔았을 때의 PROFIT의 최댓값 이라고 정의를 했다.

 

PROFIT의 최댓값이 되려면, 이전에 stock을 산 값이 최솟값이여야

Profit 즉, 판 값 - 산 값이 최댓값이 되기 때문에 

dp[i] = nums[i] - min_value라고 정의했다. 

 

코드는 다음과 같이 짰다.

 

Answer