You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints:
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
Approach
EN
KR
처음 몇 시간은 어떻게 최고 사고 파는 로직을 짜야할지 고민을 했다. 최저점에 사서 최고점에 파는게 아니고 샀다 팔았다 하면서 최대 이익을 얻는 것이 목표였기 때문에 이 부분을 어떻게 해결할지 계속 고민했었더랬다. 테스트 케이스를 도식화해서 그래프로 보니 최저점에 팔아서 가지고 있다가 최고점에 파는거나 오를때마다 파는 걸 이어 붙이는거나 같다는 걸 알았다.
주식을 가지고 있는 것 자체는 마이너스로 치진 않기 때문에 주식은 매일 산다는 가정.
처음 수익은 0부터 시작해 어제 가격보다 오늘 가격이 비싸면 그 차액만큼 수익에 더한다.그렇게 배열이 끝나면 얻은 수익을 반환한다.
여담. 이 문제의 핵심은 그리디 알고리즘이었다. 비전공자에 알고리즘을 많이 공부하지 않은 나는 들어만 봤지 한번도 제대로 공부해본 적이 없었는데 이번기회에 그리디 알고리즘에 제대로 들여다 볼 수 있었던 기회였다.
- 수익 profit 변수를 선언하고 첫 수익은 없기 때문에 0으로 시작한다.
- 어제와 오늘을 비교해야하므로 for 반복문의 시작 포인트(i)는 1로 잡아 prices 배열을 돈다.
- 만약 오늘
prices[i]이 어제prices[i-1]보다 크면(값이 오르면), 차액을 profit으로 더해준다. - 마지막으로 profit을 리턴한다.
code
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let profit = 0;
for(let i=1; i<prices.length; i++) {
if(prices[i]>prices[i-1]) {
profit += prices[i]-prices[i-1];
}
}
return profit;
};