股票利润2

这里同样使用和股票利润1差不多的动态规划方法，由于允许股票多次交易，但不允许股票同时交易，所以每天的状态只能有两个，要么手里有一只股票，要么手里没有股票。
通过当天是否有股票，可以由前一天是否有股票推断出，如果当天没有股票的话，可能前一天也没有股票，或者前一天有股票但是今天卖了。如果当天有股票的话，可能前一天没有股票但是今天买了，也可能是前一天就有股票。

PS.这里与股票利润1不同的地方在于，前一天没有股票但是今天卖了这个状态，如果是只允许操作一次，那么买股票都是从0元开始买，但是如果允许操作多次可能之前有利润。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp=[[0,0] for _ in range(len(prices))]#当天是否购买股票的两个选择

        dp[0][0]=0
        dp[0][1]=-prices[0]
        for i in range(1,len(prices)):
            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[len(prices)-1][0]

空间优化

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp=[[0,0] for _ in range(2)]#当天是否购买股票的两个选择

        dp[0][0]=0
        dp[0][1]=-prices[0]
        for i in range(1,len(prices)):
            dp[i&1][0]=max(dp[(i-1)&1][0],dp[(i-1)&1][1]+prices[i])
            dp[i&1][1]=max(dp[(i-1)&1][1],dp[(i-1)&1][0]-prices[i])
        return dp[(len(prices)-1)&1][0]

只使用两个空间，和上一个题目一样

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp=[[0,0] for _ in range(2)]#当天是否购买股票的两个选择

        dp[0]=0
        dp[1]=-prices[0]
        for i in range(1,len(prices)):
            dp[0]=max(dp[0],dp[1]+prices[i])
            dp[1]=max(dp[1],dp[0]-prices[i])
        return dp[0]

贪心法，由于现在是在求不相交的区间差值加和最大，那么其实也可以看作将为间隔为1天的区间进行相加，根据贪心法则，将所有下一个值大于当前值的值做差值，进行加和。
也可以看作是所有能实现的利润我都要，那一定是最大值。
求解出来的是最后的数值，但不代表最后的操作步骤就是这样。

贪心算法 在每一步总是做出在当前看来最好的选择。

「贪心算法」 和 「动态规划」、「回溯搜索」 算法一样，完成一件事情，是 分步决策 的；
「贪心算法」 在每一步总是做出在当前看来最好的选择，我是这样理解 「最好」 这两个字的意思：
「最好」 的意思往往根据题目而来，可能是 「最小」，也可能是 「最大」；
贪心算法和动态规划相比，它既不看前面（也就是说它不需要从前面的状态转移过来），也不看后面（无后效性（无环），后面的选择不会对前面的选择有影响），因此贪心算法时间复杂度一般是线性的，空间复杂度是常数级别的；
这道题 「贪心」 的地方在于，对于 「今天的股价 - 昨天的股价」，得到的结果有 3 种可能：① 正数，② 00，③负数。贪心算法的决策是： 只加正数 。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        sumval=0

        for i in range(1,len(prices)):
            if prices[i]>prices[i-1]:
                sumval+=prices[i]-prices[i-1]
        return sumval

也可以使用单调栈求递增区间。
入栈元素是递增的，当递增序列时，栈底元素一直都是最小值，当遇到比栈顶的元素小的元素，转折点出现，栈底和栈顶的元素需要更换，同时栈底元素也需要更换，也就是最小值需要更换，因为买卖股票的区间不能交叉。
PS. 请注意，需要为prices序列增加0值，这样如果结尾的一段或整个序列为递增，也可以把该部分的买卖利润求出来。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        stack=[]
        sumval=0
        prices.append(0)
        for i in range(len(prices)):
            while stack and prices[stack[-1]]>prices[i]:
                s=stack[-1]
                if not stack:
                    break
                sumval+=prices[s]-prices[stack[0]]
                stack=[]
            stack.append(i)
        return sumval