'''
解题思路：
动态规划
对原序列做差分，即转化成子数组的最大累加和问题
#============================================================================================
'''
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices ):
        # write code here
        L = prices
        n = len(L)

        #print(L)
        #print(n)      
        diff = []
        for i in range(1,n):
            diff.append(L[i]-L[i-1])
        #print('diff=',diff)        

        sumd = 0
        maxbargin = 0
        for i in diff:
            sumd += i
            if sumd<0:
                sumd=0
            if sumd > maxbargin:
                maxbargin = sumd
        #print('maxbargin=',maxbargin)
        return maxbargin