leetcode|weekly contest 55 Best Time to Buy and Sell Stock with Transaction Fee leetcode|leetcode

题目

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.

分析这题和之前的冷静的买卖袜子是一个题目
那我们先定义状态
buy[i] 表示第i天的买收益的最大
sell[i] 表示第i天的卖收益的最大
【leetcode|weekly contest 55 Best Time to Buy and Sell Stock with Transaction Fee】接着填写初时状态
buy[0] = - prices[0] ( 我们买了第一件）
sell[0] = 0 （没法卖，没有收益）
接着是状态转移
buy[i] = max( sell[i-1] - prices[i], buy[i-1]);
( 前一天卖了后今天买了，前一天的最大）
sell[i] = max( buy[i-1] + prices[i] - fee , sell[i-1]);
代码

class Solution { public: int maxProfit(vector& prices, int fee) { // buy[i] = max(sell[i-1]-price, buy[i-1]) // sell[i] = max(buy[i-1]+price, sell[i-1]) int n = prices.size() ; if( n <= 1 ) return 0 ; vector buy ; vector sell; buy.resize(n , 0); sell.resize( n , 0); buy[0] = - prices[0]; sell[0] = 0 ; for( int i= 1 ; i1] - prices[i] , buy[i-1] ) ; sell[i] = max( buy[i-1] + prices[i] - fee , sell[i-1] ) ; } return sell[n-1]; } };

时间复杂度O(N)空间复杂度 O(N)