首页 > 代码库 > #Leet Code# Best Time to Buy and Sell Stock
#Leet Code# Best Time to Buy and Sell Stock
描述：数组 A，对于 i < j, 找到最大的 A[j] - A[i]
代码：
1 class Solution: 2 # @param prices, a list of integer 3 # @return an integer 4 def maxProfit(self, prices): 5 if len(prices) == 0 or len(prices) == 1: 6 return 0 7 8 cur_min = prices[0] 9 max_minus = 010 11 for i in range(1, len(prices)):12 if prices[i] < cur_min:13 cur_min = prices[i]14 else:15 tmp = prices[i] - cur_min16 if tmp > max_minus:17 max_minus = tmp18 19 return max_minus
动态规划：
设dp[i]是[0,1,2...i]区间的最大利润，则该问题的一维动态规划方程如下
dp[i+1] = max{dp[i], prices[i+1] - minprices} ,minprices是区间[0,1,2...,i]内的最低价格
最大利润 = max{dp[0], dp[1], dp[2], ..., dp[n-1]}
其他思路：
按照股票差价构成新数组 prices[1]-prices[0], prices[2]-prices[1], prices[3]-prices[2], ..., prices[n-1]-prices[n-2]，求新数组的最大子段和就是最大利润
参考地址：
http://www.cnblogs.com/TenosDoIt/p/3436457.html
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。