C语言重构【714】买卖股票的最佳时机含手续费

谁践踏了优雅 2022-11-06 07:53 128阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个整数数组 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.
    注意:
    
    0 < prices.length <= 50000.
    0 < prices[i] < 50000.
    0 <= fee < 50000.

#### 方案： ####

*  dp思想，暴力dp似乎超时了，于是用last\_sell来记录稳赚不赔的卖出点，以减少循环次数，时间效率还可以，就是时间复杂度没减下来

class Solution
    { 
    public:
        int maxProfit(vector<int> &prices, int fee)
        { 
            int len = prices.size();
            if (len == 1)
                return 0;
            //用来记录那些稳赚不赔的卖出点，在判断的时候可以在此点开始，用以减少循环次数
            int last_sell = 0;
            vector<int> dp(len, 0);
            //但凡超过2的涨幅（>2）都是赚的
            for (int i = 1; i < len; i++)
            { 
                dp[i] = dp[i - 1];
                for (int j = last_sell; j < i; j++)
                { 
                    if (dp[j] + prices[i] - prices[j] - fee > dp[i])
                    { 
                        dp[i] = dp[j] + prices[i] - prices[j] - fee;
                        last_sell = j;
                    }
                }
            }
            return dp[len - 1];
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n2)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode