leetcode 714

问题

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:

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

Note:

0 < prices.length <= 50000.

0 < prices[i] < 50000.

0 <= fee < 50000.

分析

现在假设 $dp[i]$ 表示前 $i$ 个交易日所能获得的最大的利润。则 $dp[i]$ 的更新分为两种情况，一种情况是在第 $i$ 个交易日发生了卖出，另一种情况是在第 $i$ 个交易日没有发生卖出。没有发生买出，则有 $dp[i] = dp[i-1]$. 若发生了卖出，则要寻找一个 $j$ ，使得在 $j$ 发生了买入行为，则有 $dp[i] = prices[i]-prices[j]-fee+dp[j-1]$. 这时我们令 $cache = prices[j]+fee-de[j-1]$，维护这个 $cache$ 的最小值即可，很方便地在 $i$ 点求出最大利润。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int cache = INT_MAX;
        int ans = 0;
        for (int i = 0; i < prices.size(); ++i) {
            cache = min(cache, prices[i]+fee-ans);
            ans = max(ans, prices[i] - cache);
        }
        return ans;
    }
};