leetcode 【 Best Time to Buy and Sell Stock II 】python 实现

题目：

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

代码：oj测试通过 Runtime: 71 ms

 1 class Solution:
 2     # @param prices, a list of integer
 3     # @return an integer
 4     def maxProfit(self, prices):
 5         # none case or one element case
 6         if prices is None or len(prices)<2 :
 7             return 0
 8         # dp
 9         buy = 0
10         sell = 0
11         profit = 0
12         for i in range(len(prices)-1):
13             if prices[i]<=prices[i+1]:
14                 sell = i+1
15             else:
16                 profit = profit + prices[sell]-prices[buy]
17                 buy = i+1
18                 sell = i+1
19         return profit+max(0,prices[sell]-prices[buy])

思路：

采用贪心算法。

代码的逻辑还算清晰：找到最长的上升区间，最低卖最高买即可；然后再找下一个上升区间；退出循环的时候注意处理一下最后一个上升或下降区间。

for循环：

1. if的部分就是不断找更大的上升空间，找到了就一定把sell放在更利润的卖点。

2. else的部分处理的是价格下降的情况，buy和sell需要同时跟进，这样保证同样的买卖价格，做到不赔钱

有一个梗：代码AC后，我review时发现if和else里面都有sell=i+1这个语句，那么既然不管是if或else都得执行sell=i+1，为啥还要在每个语句里面单拎出来呢？于是就有了下面的代码（这部分代码是错误举例用的）：结果竟然是报错。

            sell = i+1
            if prices[i]>prices[i+1]:
                profit = profit + prices[sell]-prices[buy]
                buy = i+1

这是一个思维的陷阱：不错，确实在if和else里面都执行了sell=i+1这个语句，但是语句执行的逻辑顺序是不一样的。请注意，如果是prices[i]>prices[i+1]的条件下，sell=i+1是在profit语句之后执行的。于是恍然大悟，修改成如下的代码：

oj测试通过 Runtime: 67 ms

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        # none case or one element case
        if prices is None or len(prices)<2 :
            return 0
        # dp
        buy = 0
        sell = 0
        profit = 0
        for i in range(len(prices)-1):
            if prices[i]>prices[i+1]:
                profit = profit + prices[sell]-prices[buy]
                buy = i+1
            sell = i+1
        return profit+max(0,prices[sell]-prices[buy])

这样代码的逻辑就更简洁了，可以解释如下：只要相邻两天，后一天比前一天高就可以低买高卖产生利润。

第二个更简洁的代码，似乎也是网上更多的人列出来的答案。简洁的解法也可以由一般的解法推演出来。