LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee (Java版; Medium)

淩亂°似流年 2023-07-18 06:16 13阅读 0赞

### [welcome to my blog][] ###

## LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee (Java版; Medium) ##

#### 题目描述 ####

Your are given an array of integers prices, for which the i-th element is the price of a given stock 
    on day i; and a non-negative integer fee representing a transaction fee.
    
    You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share 
    before you buy again.)
    
    Return the maximum profit you can make.
    
    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.
    Note:
    
    0 < prices.length <= 50000.
    0 < prices[i] < 50000.
    0 <= fee < 50000.

#### 第一次做; 在卖出时交手续费 核心: 1)dp\[i\]\[0\]表示第i天不持有股票时的最大利润; dp\[i\]\[1\]表示第i天持有股票时的最大利润 ####

class Solution { 
        public int maxProfit(int[] prices, int fee) { 
            if(prices==null || prices.length==0){ 
                return 0;
            }
            int n = prices.length;
            /* dp[i][0]表示第i天不持有股票时的最大利润 dp[i][1]表示第i天持有股票时的最大利润 */
            int[][] dp = new int[n][2];
            dp[0][1] = -prices[0];
            for(int i=1; i<n; i++){ 
                dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]-fee); //卖出的时候交手续费
                dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
            }
            return dp[n-1][0];
        }
    }

#### 第一次做; 在买入时交手续费, 初始化条件为dp\[0\]\[1\] = -prices\[0\]-fee; ####

class Solution {
        public int maxProfit(int[] prices, int fee) {
            if(prices==null || prices.length==0){
                return 0;
            }
            int n = prices.length;
            /*
            dp[i][0]表示第i天不持有股票时的最大利润
            dp[i][1]表示第i天持有股票时的最大利润
            */
            int[][] dp = new int[n][2];
            dp[0][1] = -prices[0]-fee;
            for(int i=1; i<n; i++){
                dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
                dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]-fee);//买入的时候交手续费的话, 需要改变初始条件为dp[0][1] = -prices[0] - fee;
            }
            return dp[n-1][0];
        }
    }

[welcome to my blog]: https://littlehaes.com