算法導論——python實踐（4.1最大子數組問題）

最大子數組問題描述：尋找數組A的和最大非空連續子數組

4.1.1暴力求解

簡單的嘗試對每對可能存在的子數組的和進行計算，長度為n的數組總共有n*(n+1)/2中可能

#  最大子數組問題暴力求解
def find_key(dict):
    new_keylist=[]
    b=max(dict,key=dict.get)#找出dict中的值最大值所對應的關鍵字（這裡表示最大子數組）
    print (dict[b])
    for key in dict:
        if dict[key]==dict[b]:
            new_keylist.append(key)#可能存在多個最大子數組的情況
    return new_keylist

a=[100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97]#原始資料
b=[]
for i in range(1,len(a)):
    b.append(a[i]-a[i-1])  #增量數組
print (b)
new=[]
d={}
for i in range(0,len(b)):   #子數組長度為i
    for j in range(0,len(b)-i):
        key=sum(b[j:1+j+i])
        new=tuple(b[j:1+j+i])
        d[new]=key
v=list(d.values())
print (d)
print (find_key(d))
           

具體思路是：将算出和的數組作為字典d的關鍵字，算出的和作為d的相對應的關鍵字的和，在find_key函數中， b=max(dict,key=dict.get)是為了找出dict中的值最大值所對應的關鍵字（這裡表示最大子數組），由于可能存在多個最大子數組的情況，這裡可以将其都列印出來。

4.1.2使用分治政策的求解方法

分治解法詳解

find_max_crossing函數是求解跨越重點的最大子數組，傳回一個下标元組劃定跨越中點的最大子數組的邊界，并傳回最大子數組的值的和，find_max_subarray是遞歸函數，對于每個分解後的數組，其最大子數組問題都隻有三種可能：完全位于數組A的左半邊，完全位于數組A的右半邊，跨越了中點，是以可使用分治政策，對每個遞歸的數組，求解三種情況下的最大子數組，并進行比較和的大小，進而确定最大子數組的上下标的邊界。遞歸終止條件：當分解後的數組中隻有一個元素時，該數組的最大子數組就是其本身。

#  最大子數組問題
import math
def find_max_crossing(seq,low,mid,high):
    left_sum = float("-inf")#定義個無窮小的數值
    sum=0
    for i in range(mid,low-1,-1):
        sum=seq[i]+sum
        if sum>left_sum:
            left_sum=sum
            max_left=i
    sum=0
    right_sum=float('-inf')
    for j in range(mid+1,high+1):
        sum=seq[j]+sum
        if sum>right_sum:
            right_sum=sum
            max_right=j
    return [max_left,max_right,left_sum+right_sum]


def find_max_subarray(seq,low,high):

    if high==low:#遞歸終止條件
        return[low,high,float(seq[low])]
    else:
        mid=((low+high)//2)

        [left_low,left_high,left_sum]=find_max_subarray(seq,low,mid)

        [right_low,right_high,right_sum]=find_max_subarray(seq,mid+1,high)

        [cross_low,cross_high,cross_sum]=find_max_crossing(seq,low,mid,high)


        if (left_sum>=right_sum)and(right_sum>=cross_sum):
            return [left_low,left_high,left_sum]
        elif (right_sum>=left_sum)and(right_sum>=cross_sum):
            return [right_low,right_high,right_sum]
        else:
            return [cross_low,cross_high,cross_sum]
a=[100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97]#原始資料
b=[]
for i in range(1,len(a)):
    b.append(a[i]-a[i-1])  #增量數組
print (b)
print(find_max_subarray(b,0,len(b)-1))
           

參考文獻：

1.算法導論 機械工業出版社 第四章第一節 最大子數組問題。