C++实现LeetCode(122.买股票的最佳时间之二)

下面是详细讲解“C++实现LeetCode(122.买股票的最佳时间之二)”的完整攻略。

什么是买股票的最佳时间问题

买股票的最佳时间问题是一个经典的动态规划问题，其求解目标是：给定一组股票价格，求出在给定的时间范围内，我们应该在哪些时间买入和卖出股票，才能获取最大收益。

LeetCode的买股票的最佳时间问题

针对该问题，LeetCode中的 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ 给出了一道非常经典的问题：买股票的最佳时间之二。题目描述如下：

问题： 给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例

输入: [7,1,5,3,6,4]

输出: 7

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出，这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，这笔交易所能获得利润 = 6 - 3 = 3 。

思路

根据题目，我们可以发现一下几个规律：

1. 可以进行多次交易，即如果在第i天前能获得利润，那么第i天的股票价格当天买进、明天卖出所获得的利润是相等的；

2. 利润可以累加，即如果第i天和第j天进行交易获得利润，那么第i天买进、第j天卖出所获得的利润等于第i天买进、第j-1天卖出所获得的利润加上第j天卖出和第j-1天买进所获得的利润。

根据这两个规律，我们可以定义动态规划转移方程如下：

$$dp[i] = dp[i-1] + (price[i] - price[i-1])\ where\ price[i] > price[i-1]$$

其中，$dp[i]$表示第i天所能获得的最大利润，$price[i]$表示第i天的股票价格。上式中的$price[i] - price[i-1]$即为股票在第i天和第i-1天的价格差，如果这个差值大于0，则说明可以在这两天之间获得利润，因此我们将这个差值加入到$dp[i-1]$中。

如果上式中的条件不满足，则说明在第i天不能获得利润，并且也不能进行交易。总的来说，如果数组中的元素个数为n，那么当天我们有两种决策：

1. 如果$price[i] > price[i-1]$，则我们可以选择在第i-1天买入，在第i天卖出，也可以选择不进行任何操作。

2. 如果$price[i] \leq price[i-1]$，则我们不能进行任何操作。

因此，我们只需要求出所有可以获得利润的差值并求和，就可以得到最大的利润。时间复杂度为O(n)，空间复杂度为O(1)。

代码

下面是用C++实现的代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i-1]) {
                ans += (prices[i] - prices[i-1]);
            }
        }
        return ans;
    }
};

示例说明

这里给出两个示例：

示例1

输入:

[7,1,5,3,6,4]

输出：

7

解释：

在第2天（股票价格 = 1）的时候买进，在第3天（股票价格 = 5）的时候卖出，可以获得4元的利润。

在第4天（股票价格 = 3）的时候买进，在第5天（股票价格 = 6）的时候卖出，可以获得3元的利润。

因此，总的最大利润为7元。

示例2

输入：

[1,2,3,4,5]

输出：

4

解释：

在第1天（股票价格 = 1）的时候买进，在第5天（股票价格 = 5）的时候卖出，可以获得4元的利润。

因此，总的最大利润为4元。