<每日一題>演算法導論:最大股票收益

NO IMAGE

一.抽象:
給定一個陣列,求出陣列中兩數之差的最大值,被減數下標大於減數
二.方法:
1.分治法:
a.將陣列分成左右兩部分
b.分別求出兩部分的最大值,最小值,以及下標大的數與下標小的數之差的最大值。
c.合併兩部分的結果

時間為O(nlogn)

2.轉化為最大子陣列和問題:
a.先求出陣列的前一個數與後一個數之差,組成新的陣列
b.求新陣列的最大子陣列和
(原理:假設原陣列(長度為n)為l[0…n-1],新陣列為d[0…n-2],其中d[i]=l[i 1]-l[i],當求出d的最大子陣列為d[x…y]時,則有:
l[x 1]-l[x] l[x 2]-l[x 1] … l[y 1]-l[y] = l[y 1]-l[x]
也就求得原陣列兩數之差的最大值)

時間為O(n)

三.程式碼(python ):
1.分治法:

def get_max_diff_partition(l,start,end)
mid=int((start end)/2)
#Max對應陣列從start到end的最大值
#Min對應陣列從start到end的最小值
#d_max對應陣列從start到end的下標大的數與下標小的數之差的最大值
if start==end:
Max=l[start]
Min=l[start]
d_max=0
return Min,Max,d_max
Max_l,Min_l,d_max_l = get_max_diff_partition(l,start,mid)
Max_r,Min_r,d_max_r = get_max_diff_partition(l,mid 1,end)
#合併左右兩個陣列
d_max_mid = Max_r - Min_l
d_max = max(d_max_l,d_max_mid,d_max_r)
Min=min(Min_l,Min_r)
Max=max(Max_l,Max_r)
return Min,Max,d_max

2.最大子陣列法:

def get_diff_max_best(l):
length=len(l)
#求出前一天與後一天的差值
diff=[]
for i in range(length-1):
diff.append(l[i 1]-l[i])
max_sum=0
cur_sum=0
for d in diff:
if cur_sum d>0:
cur_sum =d
else:
cur_sum=0
if cur_sum>max_sum:
max_sum=cur_sum
return max_sum