出现概率：约20%。这道题目可能以买卖股票的最佳时机，或者最大抬升等各种形式出现，这也是一道动态规划的史诗级范例。呦呵，又整上两重循环了，这循环写的很可以啊。
参考代码：
def max_drawdown(arr):
assert len(arr)>2, "len(arr) should > 2!"
x,y = arr[0:2]
xmax = x
maxdiff = x-y
for i in range(2,len(arr)):
if arr[i-1] > xmax:
xmax = arr[i-1]
if xmax - arr[i] > maxdiff:
maxdiff = xmax - arr[i]
x,y = xmax,arr[i]
print("x=",x,",y=",y)
return(maxdiff)
print(max_drawdown([3,7,2,6,4,1,9,8,5]))
输出结果：
x= 7 ,y= 16
6，合并两个有序数组
题目形式：给定两个按升序排列的有序数组，将它们合并成一个新的有序数组。例如：a = [1,2,6,8], b = [2,4,7,10]，输出为 arr = [1,2,2,4,6,7,8,10]
题目难度：简单。
出现概率：约15%。这道题目考察的是归并排序的基本思想。注意，这两个数组是有序的呢，你怎么可以无视这么有利的条件直接拼接上两个数组开始冒泡了？？？
参考代码：
def merge_sorted_array(a,b):
c = []
i,j = 0,0
while True:
if i==len(a):
c.extend(b[j:])
return(c)
elif j==len(b):
c.extend(a[i:])
return(c)
else:
if a[i]<b[j]:
c.append(a[i])
i=i+1
else:
c.append(b[j])
j=j+1
print(merge_sorted_array([1,2,6,8],[2,4,7,10]))
输出结果：
[1, 2, 2, 4, 6, 7, 8, 10]
7，最大连续子数组和
题目形式：给定一个数组，求其最大连续子数组的和。例如：arr = [1,5,-10,2,5,-3,2,6,-3,1]. 输出为：12。对应的连续子数组为 [2,5,-3,2,6]。
题目难度：中等。
出现概率：约15%。这道题目也是一道动态规划的祖传范例。同学，你的这个两重循环写的确实很6，但是我们不能认为你的这道题目做对了！
参考代码：
def max_sub_array(arr):
n = len(arr)
maxi,maxall = arr[0],arr[0]
for i in range(1,n):
maxi = max(arr[i],maxi + arr[i])
maxall = max(maxall,maxi)
return(maxall)
print(max_sub_array([1,5,-10,2,5,-3,2,6,-3,1]))
输出结果：
12
8，最长不重复子串
题目形式：给定一个字符串，找出没有重复字符的最长的子串。例如输入“abcbefgf”，答案是 “cbefg”。
题目难度：困难。
出现概率：约10%。这是一道动态规划+哈希查找的综合应用题。这道题能做出来，你的代码功底很可以啊。对了，你的期望薪资是多少？
参考代码：
def longest_substr(s):
dic = {}
start,maxlen,substr = 0,0,""
for i,x in enumerate(s):
if x in dic:
start = max(dic[x]+1,start)
dic[x] = i
else:
dic[x] = i
if i-start+1>maxlen:
maxlen = i-start+1
substr = s[start:i+1]
return(substr)
print(longest_substr("abcbefgf"))
print(longest_substr("abcdef"))
print(longest_substr("abbcddefh"))
输出结果：
cbefgabcdefdefh
9，全排列
题目形式：给定一个数组，找出其所有可能的排列。例如: arr = [1,1,3]，输出为 [[1,1,3],[1,3,1],[3,1,1]]。
题目难度：中等