题目描述

假定你知道某只股票每一天价格的变动。
你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。
请设计一个函数，计算你所能获得的最大收益。

方法一 贪心算法

解题思路

因为可以进行无限次交易，因此只要后一天价格高于前一天，我们就应该买入前一天的并且在后一天卖出；如果后一天价格低于前一天，则不进行操作。最后的利润为折线图中上升部分的总和。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // 总利润
        int profits = 0;
        int len = prices.size();
        for(int i = 1;i < len; i++){
            // 如果后一天利润高于前一天
            if(prices[i] > prices[i - 1]){
                // 前一天买入，后一天卖出
                profits += prices[i] - prices[i - 1];
            }
        }
        return profits;
    }
};

复杂度分析

• 时间复杂度：需要遍历一次数组，时间复杂度为
• 空间复杂度：使用了常数个变量，空间复杂度为

方法二 动态规划

解题思路

也可以从动态规划的角度思考这个问题。设为第天时得到的最大利润。

• 如果第天不卖出，
• 如果第天卖出，设为第天买入，则

为了取利润的最大值，需要遍历，如果不进行优化，时间复杂度为$。因为对一个固定的，固定不变，所以可以用变量存储的最大值，这样，只需要遍历一次数组，时间复杂度优化为。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        // 动态规划数组f[]和优化所使用的变量sub_max
        int f[len + 1], sub_max = -prices[0];
        // 初始条件
        f[0] = 0;
        for(int i = 1;i < len; i++) {
            // 更新动态规划数组f[]
            f[i] = max(f[i - 1], sub_max + prices[i]);
            // 更新变量sub_max
            sub_max = max(sub_max, f[i - 1] - prices[i]);
        }
        return f[len - 1];
    }
};

复杂度分析

• 时间复杂度：需要遍历一次数组，时间复杂度为
• 空间复杂度：为了进行动态规划，使用了辅助数组，空间复杂度为