
1. 문제 분석
문제분석
--------------------
- 정수배열 prices, prices[i]는 i번째 날짜의 주가이다.
- 매일 주식을 사거나 팔 수 있다.
- 주식은 최대 1개만 가질 수 있다.
- 그날 사서 같은 날에 팔 수도 있다.
- 최대 이익을 반환하라.
제한조건
--------------------
- 1 <= prices.length <= 3 * 10^4
- 0 <= prices[i] <= 10^4
2. 접근 방법
접근방법
--------------------
이전 문제와 달리 한번만 사고 파는 것이 아닌 여러번 사고 팔수 있다.
즉, profit이 누적될 수 있다는 뜻이다.
3. 코드
var maxProfit = function(prices) {
let buyPrice = prices[0];
let profit = 0;
for (let i = 1; i < prices.length; i++) {
let sellPrice = prices[i];
if (sellPrice > buyPrice) {
profit += (sellPrice - buyPrice)
}
buyPrice = prices[i]
}
return profit;
};
- 이익이 생겼을 때만 이익에 누적하여 최대 이익을 구한다.
내가 머릿 속으로 유념했던 부분은 [7, 1, 5, 1, 7, 9, 6] 으로 주어졌을 때,
최대 이익은 (5 - 1) + (9 - 1) = 12 인데, 위 로직대로는 (5 - 1) + (7 - 1) + (9 - 7) = 12 로 계산되는 것이었다.
두 방법 모두 동일한 최대 이익을 구하는데 그렇지 않은 예외 케이스가 있을지 생각해보게되었다.
4. 복잡도 분석
- 시간복잡도: O(n)
- 공간복잡도: O(1)
'Leetcode' 카테고리의 다른 글
[Leetcode] 45. Jump Game II - JS (0) | 2024.09.12 |
---|---|
[Leetcode] 55. Jump Game - JS (0) | 2024.09.11 |
[Leetcode] 121. Best Time to Buy and Sell Stock - JS (1) | 2024.09.09 |
[Leetcode] 189. Rotate Array - JS (0) | 2024.08.21 |
[Leetcode] 169. Majority Element - JS (0) | 2024.08.20 |