题解 | #买卖股票的最好时机#

按照动态规划的思路分解问题。
令dp[i]为以第i天为卖出点的最大收益，而不去管是从哪天开始买入得。
那么dp[i+1]=dp[i] + p[i+1], 其中p[i+1] 为第i+1天的收入。不过这有个前提就是dp[i+1]>=0, 最大收益不能为负，因为可以当天买卖收益为0.

#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices ):
        # write code here
        n = len(prices)
        if n<=1:
            return 0
        dplast = 0    #上一天为卖出点的最大收益值
        maxp = dplast    #最大收益指
        for i in range(1, n):    #从第二天开始遍历
            p = prices[i]-prices[i-1]    #当前天相比前一天的收益值
            if dplast+p > 0:    #前一天为卖出点的最大收益加上今天的收益指，即为以今天为卖出点的最大收益，dp[i] = dp[i] + p[i] 
                dplast += p
            else:                #不过收益指不能小于0，因为最差情况就是当天买卖，收益为0。
                dplast = 0
            maxp = max(maxp, dplast)
        return maxp