Description

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

---

prices 배열이 주어지고, prices[i]는 i번째 날의 주식 가격을 나타냅니다. 또한 정수 fee는 거래 수수료를 의미합니다.

가능한 최대 이익을 구하세요. 원하는 만큼 많은 거래를 완료할 수 있지만, 각 거래마다 수수료를 지불해야 합니다.

참고:

• 여러 거래를 동시에 진행할 수 없습니다 (즉, 다시 구매하기 전에 주식을 팔아야 합니다).
• 거래 수수료는 각 주식 구매 및 판매시 한 번만 부과됩니다.

예제 1:

입력: prices = [1,3,2,8,4,9], fee = 2
출력: 8
설명: 최대 이익은 다음과 같이 달성할 수 있습니다:

• prices[0] = 1에 구입
• prices[3] = 8에 판매
• prices[4] = 4에 구입
• prices[5] = 9에 판매
  총 이익은 ((8 - 1) - 2) + ((9 - 4) - 2) = 8입니다.

예제 2:

입력: prices = [1,3,7,5,10,3], fee = 3
출력: 6

제약 사항:

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

Solution

public class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        int[] dp = new int[2]; // dp[0]은 주식을 소유하지 않은 상태, dp[1]은 주식을 소유한 상태

        dp[0] = 0;          // 첫날 주식을 소유하지 않은 상태의 이익은 0
        dp[1] = -prices[0]; // 첫날 주식을 소유한 상태의 이익은 주식을 산 가격의 음수

        for (int i = 1; i < n; i++) {
            int temp = dp[0];
            dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee); // 주식을 팔지 않거나 팔고 수수료를 뺀 경우
            dp[1] = Math.max(dp[1], temp - prices[i]);        // 주식을 사지 않거나 새로 사는 경우          
            System.out.println("ith: " + i + ", price: " + prices[i] + ", dp[0]: " + dp[0] + ", dp[1]: " + dp[1]);
        }

        return dp[0]; // 마지막 날 주식을 소유하지 않은 상태에서의 최대 이익 반환
    }
}

추가 테스트 케이스

Input

prices =[1,3,2,8,10,4,9]
fee = 2

Stdout

ith: 1, price: 3, dp[0]: 0, dp[1]: -1
ith: 2, price: 2, dp[0]: 0, dp[1]: -1
ith: 3, price: 8, dp[0]: 5, dp[1]: -1
ith: 4, price: 10, dp[0]: 7, dp[1]: -1
ith: 5, price: 4, dp[0]: 7, dp[1]: 3
ith: 6, price: 9, dp[0]: 10, dp[1]: 3

Output

10

Expected

10