122. 买卖股票的最佳时机 II

题目

• 题号：122
• 难度：简单
• https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例1

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

实现

思路1

因为题目只要求输出最大利润，并且允许多次购买一只股票，所以我们可以发现一个求得最大利润的策略：只要当天股票价格大于前一天就选择继续保持买入状态，即将两天的价格加入最大利润计算的变量中；若当天股票小于前一天时就假定股票在前一天卖出，此时不需要计算价格差。这样在遍历数组中，只要有价格的增益我们就会将增益加入总利润中，求得的就肯定是最大利润。
这也让我们发现此题的本质：其实就是把股票价格增长的所有价格全部累加即可。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxprofit = 0
        for i in range(1, len(prices)):
            maxprofit += (prices[i]-prices[i-1]) if prices[i]>prices[i-1] else 0
        return maxprofit

时间复杂度：
空间复杂度：
**

思路2 动态规划

查看别人题解想到的方案。
状态：首先先定义状态dp[i][0]表示第i天交易完手里没有股票的最大利润，dp[i][1]表示第i天交易完手里有股票的最大润。
转移方程：

1. 先来考虑dp[i][0]，因为这一天交易后手里没股票，所以前一天的状态有以下两种情况：
   1. 也没股票，即dp[i-1][0]；
   2. 有股票，即dp[i-1][1]，但该情况下今天必定将股票卖出了，获利prices[i]。

所以该情况下的动态转移方程就为：

1. 再考虑dp[i][1]，因为这一天交易后手里有股票，所以前一天的状态有以下两种情况：
   1. 已持有股票，即dp[i-1][1]；
   2. 没有股票，即dp[i-1][1]，但该情况下今天必定买入股票，花费prices[i]。

所以该情况下的动态转移方程就为：

初始状态：
dp[0][0]=0，dp[0][1]=-prices[0]

然后我们从前往后计算填充这个dp数组即可。值得注意的是最后股票卖出能使最大利润更高，所以最后答案就是dp[n-1][0]。

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

时间复杂度：
空间复杂度：