又到了晚上，动态规划，开刷！
第121题 Best Time to Buy and Sell Stock
题目的意思：给予一个数组price，表示特定股票在某天的股价，里面第i个数表示第i天的价格。只能交易一次（买一次+卖一次），求最大利润
分析：典型的动态规划。当我们要求到第i天为止最大的利润，就需要知道i-1天为止的最大利润，然后用第i天的股价减去(i-1)天股票最低值，然后比较即可。所以我们可以推出状态转移方程：
maxProfit(i) = max(maxProfit(i-1), price[i] - min(price[:i]))
下面是代码：
class Solution:
# @param {integer[]} prices
# @return {integer}
def maxProfit(self, price):
maxprofit = 0
nextprofit = 0
profit = 0
if len(price) <= 1:
return 0
for i in range(1, len(price)):
nextprofit = max(profit, price[i] - min(price[:i]))
maxprofit = max(maxprofit, nextprofit)
profit = nextprofit
return maxprofit
可是这样提交上去，返回了一个运行超时..(未通过) 但是大体思路是正确的，所以我就想对这个程序进行改进。我注意到这几个min,max函数上。要知道，虽然我们使用了这个python提供的函数，但是python的实现过程肯定不是O(1)，肯定内部实现是需要排序的，这里就和我的遍历重复了！ 所以我在for循环外添加了一个变量minNum：minNum = price[0]用来记录最小值，然后在for循环中进行了如下修改：
for i in range(1, len(price)):
if price[i] < minNum:
minNum = price[i]
else:
nextprofit = max(profit, price[i] - minNum)
maxprofit = max(maxprofit, nextprofit)
profit = nextprofit
第53题 Maximum Subarray
题目的意思：求和为最大的子串，例如数组[−2,1,−3,4,−1,2,1,−5,4]，它的最大子串为[4,−1,2,1]，和为6
分析：如果当前和为负数，后面的数值加上当前和则必然小于原数值，则应将当前和丢弃
class Solution:
# @param {integer[]} nums
# @return {integer}
def maxSubArray(self, nums):
cursum = 0
maxsum = -2147483648
for i in range(len(nums)):
if cursum <= 0:
cursum = nums[i]
else:
cursum += nums[i]
maxsum = max(maxsum, cursum)
return maxsum
该题的变种：给一个数组，求这个数组中子序列和最大的最短子序列
比如数组a[]={1,2,2,-3,-5,5}子序列和最大为5，最短的为a[5]
分析：首先，我们可以用上面的方法求出和最大的序列和，但是这里我们可以使用一个字典来储存这个子序列。当遇到两个子序列和一样的时候，比较子序列长度，取长度小的那个。下面是代码：
def maxSum(li):
cursum = 0
maxsum = -2147483648
templist = [] #增加一个临时列表变量，用于记录子序列
shortDict = dict()
for i in range(len(li)):
if cursum > 0:
cursum += li[i]
templist.append(li[i]) #把该元素推入列表中
else:
cursum = li[i]
templist[:] = [] #此时cursum<=0,不符合条件，所以清空列表
templist.append(li[i]) #把该元素推入数组中
if maxsum > cursum:
pass
if maxsum < cursum:
maxsum = cursum
shortDict[maxsum] = templist[:]
if maxsum == cursum: #当最大和等于当前和的时候，比较二者对应子序列长度
if len(shortDict[maxsum]) > len(templist):
shortDict[maxsum] = templist[:]
return shortDict[maxsum]
在这里，有个比较有意思的点：
假设我把某列表复制给了字典某键对应的值：tempDict[key] = templist, 然后再对该列表进行操作，则这个字典的键对应的值也会发生改变！因为直接使用等号+列表名是浅复制，只是把列表的地址复制给了字典，所以对列表的任何改变都会导致dict的改变！
我需要做的就是对列表进行深复制~ 深复制的方法很简单：
方法1.
简单列表的拷贝
已知一个列表，求生成一个新的列表，列表元素是原列表的复制
a=[1,2]
b=a[:]
这样, 修改a对b没有影响。修改b对a没有影响。
方法2.
可以使用copy模块中的deepcopy函数。修改测试如下：
import copy
a=[1,2]
b=copy.deepcopy(a)