#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 = 0
10 
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_min
16                 if tmp > max_minus:
17                     max_minus = tmp
18 
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