动态规划——买卖股票最佳时机

思路：动态规划，找到状态转移，以及如何初始化dp。如果使用dp数组，空间复杂度为O(n)。不使用dp数组，可以优化到O(1)。dp定义为，前i天可以获得的最大利润。

def maxProfit(nums): n=len(nums) dp=0 #dp初始化 minPrice=nums[0] for i in range(n): minPrice=min(minPrice,nums[i]) dp=max(dp,nums[i]-minPrice) #状态转移 print(dp) return dp def main(): line=input().strip() if not line: return nums=list(map(int,line.split())) maxProfit(nums) if __name__=="__main__": main()