[LeetCode] Best Time to Buy and Sell Stock with Transaction Fee

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/?envType=study-plan-v2&envId=leetcode-75

You are given an array prices where prices[i] is the price of a given stock on the ith day, 

and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. 

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note:
You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
The transaction fee is only charged once for each stock purchase and sale.
 

Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
 

Constraints:
1 <= prices.length <= 5 * 104
1 <= prices[i] < 5 * 104
0 <= fee < 5 * 104

---

i 번째 날의 주식 가격이 나타난 prices라는 배열과 매도 수수료 fee가 주어진다.

prices 동안 주식을 사고 팔아서 얻을 수 있는 최대 수익을 구하는 문제다.

 

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    // fee 매매수수료(매도할때만 청구됨)
    // prices[i] = i번째날의 주식 가격
    // 사고 팔아서 얻을 수 있는 최대 수익 구하기
    // 아예 안 사는 게 이득일 수도 있음. => 0 리턴
    
    let own = -prices[0]; // 첫날 주식 삼
    let cash = 0; // 첫날 안샀음

    for(let price of prices){
        // 살 때가 이득인지 안 사는 게 이득인지
        own = Math.max(own, cash - price);
        // 가진 걸 팔았을 때가 이득인지 갖고 있는 게 이득인지
        cash = Math.max(cash, own + price - fee); 
    }

    return Math.max(own, cash);
};

 

단순히 샀을 때와 안 샀을때로 나눠 상태를 관리하고,

cash는 주식을 판매했거나 사지 않았을 때의 현금량, own은 주식을 구매한 후의 현금량이다.

샀을 때는 가진 걸 파는 게 이득인지, 계속 갖고 있는 게 이득인지 판별한다.

가진 주식이 없을 때는 사는 게 이득인지 안 사는게 이득인지 판별한다.

 

첫 번째 예시 [1, 3, 2, 8, 4, 9] 에 대해서는 아래처럼 진행할 수 있다.

 

Day	prices[i]	own	cash
0	1	-1	0
1	3	max(-1, 0 - 3) = -1	max(0, -1 + 3 - 2) = 0
2	2	max(-1, 0 - 2) = -1	max(0, -1 + 2 - 2) = 0
3	8	max(-1, 0 - 8) = -1	max(0, -1 + 8 - 2) = 5
4	4	max(-1, 5 - 4) = 1	max(5, 1 + 4 - 2) = 5
5	9	max(1, 5 - 9) = 1	max(5, 1 + 9 - 2) = 8

 

이렇게 각각 판별 후에 더 큰 값을 덮어써 저장하고, 마지막에 결국 뭐가 더 큰지 판별해서 리턴하면 끝~.~