算法优化：最大字段和，双指针遍历(n^2)，分治法(nlogn)，动态规划(n)
生活随笔
收集整理的這篇文章主要介紹了
算法优化：最大字段和，双指针遍历(n^2)，分治法(nlogn)，动态规划(n)
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
最大字段和，有點(diǎn)類似與最長(zhǎng)公共子序列，這里是求連續(xù)一段求和最大的一段，比如[-2,11,-4,-4,13,-5,-2]最大求和的連續(xù)一段為11,-4,-4,13，和為16.
最基本的雙針模型遍歷，兩個(gè)指針，分別代表最大和序列的起始和終止,算法時(shí)間復(fù)雜度O(n^2)
# 以下算法時(shí)間復(fù)雜度O(n^2) def maxSum(arr):num = len(arr)# 記錄最好的結(jié)果，這個(gè)結(jié)果是一個(gè)不斷逼近的過程best_result_start =0best_result_end=0best_result =0# i為起始的指針，j為終止的指針，基于簡(jiǎn)單計(jì)算，起始位置不可能為負(fù)的，因?yàn)榧偃?/span># 為負(fù)的，后移一位就會(huì)使結(jié)果變大for i in range(num):if arr[i] <0:continueelse:cur_sum = arr[i]# j指針后移更新當(dāng)前的求和for j in range(i+1,num):cur_sum +=arr[j] # 假如當(dāng)前求和大于當(dāng)前的最好結(jié)果，就更新當(dāng)前的最好結(jié)果if cur_sum > best_result:best_result = cur_sumbest_result_start =ibest_result_end = jreturn best_result,best_result_start,best_result_end分治的算法：分成2段，3中情況考慮，取其最大,算法時(shí)間復(fù)雜度O(nlogn)之間
#%% # 基于分治的做法，把數(shù)組分成兩個(gè)部分，最優(yōu)解出現(xiàn)的情況：要么在左半邊，要么在右半邊， # 左邊的尾部+右邊頭部 # 針對(duì)起始為left,求最長(zhǎng)字段和并返回，終止的標(biāo)號(hào) def start_max(arr,left,right):cur_sum =0best_result =0best_result_end =0for i in range(left,right+1):cur_sum += arr[i] if cur_sum > best_result:best_result = cur_sumbest_result_end = ireturn best_result,best_result_end# 針對(duì)起始為right,求最長(zhǎng)字段和并返回，終止的標(biāo)號(hào) def end_max(arr,left,right):cur_sum =0best_result =0best_result_end =0for i in range(right,left-1,-1):cur_sum += arr[i] if cur_sum > best_result:best_result = cur_sumbest_result_end = ireturn best_result,best_result_end # 遞歸的理解，一種直接看成遞歸到最底層，然后在最底層的處理，一種直接看成某一層直接把遞歸函數(shù)看成 # 你要用的變量 # 關(guān)于return和不return的理解，當(dāng)你需要返回結(jié)果的時(shí)候就需要返回，在原來數(shù)組上操作的情況就可以不返回 def maxSumSub(arr,left,right):# 遞歸的出口，也就是最小子問題的解if left == right:best_sum = max(0,arr[left])best_i = leftbest_j = rightelse:# 劃分子問題的過程，一層層進(jìn)入遞歸，子問題不斷劃分，dividemid = left + (right-left)//2# 針對(duì)子問題處理，此時(shí)三個(gè)子問題# 最優(yōu)解在左邊left_max,left_i,left_j = maxSumSub(arr,left,mid)# 最優(yōu)解在右邊right_max,right_i,right_j = maxSumSub(arr,mid+1,right)# 最優(yōu)解出現(xiàn)在左邊的尾部+右邊頭部，最優(yōu)解和起止位置best_left,best_i = end_max(arr,left,mid)best_right,best_j =start_max(arr,mid+1,right)best_sum = best_left+ best_right# 最優(yōu)解取三者中的最大值if best_sum < left_max:best_sum = left_maxbest_i = left_ibest_j = left_j if best_sum < right_max:best_sum = right_maxbest_i = right_ibest_j = right_j return best_sum,best_i,best_j動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)，狀態(tài)方程為：b[j] = max{b[j-1]+arr[j],arr[j]}，b[j]為終點(diǎn)為j的最大字段和，原問題最優(yōu)解就是b[j]的最大值,明顯這個(gè)是O(n)的時(shí)間復(fù)雜度。還是有必要說明一下，這里的 動(dòng)態(tài)規(guī)劃并沒有對(duì)原問題進(jìn)行動(dòng)態(tài)規(guī)劃，而是對(duì)原問題的某個(gè)解進(jìn)行動(dòng)態(tài)規(guī)劃，或者說原問題的動(dòng)態(tài)規(guī)劃方程為max{max{b[j-1]+arr[j],arr[j]}}
#%% # 動(dòng)態(tài)規(guī)劃的算法，狀態(tài)方程，初始值 # 如何劃分子問題比較好了，看成選擇問題，選與不選，從尾部開始，i選的話，最大值就是end_max前面 # n-1個(gè)元素的最大值+arr[i],不選的話就是前面n-1個(gè)元素求最小字段和 # 這個(gè)工作量好大，問題規(guī)模縮小了1，然后干了分治算法一層的工作量 # 所以這種規(guī)約子問題的方案不好？ # 最大字段結(jié)束在j,那么原問題的解就是j=0,1,2..len(arr)-1 # 這么多情況里面的最大值， # 我們定義b[j]為結(jié)束在j字段和最大值，max{b[j]} 0<=j<=len(arr)-1 # 我們只要求出了每一個(gè)b[j],最大值就是可以從里面求出來了 # 那么b如何求解了,結(jié)束在j的最大字段和，假如前面j-1最大字段和小于0的話，那就是arr[j] # 狀態(tài)方程為：b[j] = max{b[j-1]+arr[j],arr[j]} # 這里不需要考慮arr[j]是否大于0，因?yàn)槲业淖訂栴}就是定義的是結(jié)束在j的最大字段和，至于 # 最終的解是結(jié)束在不同的j上的最大字段和的最大值。# 這個(gè)方法可以知道結(jié)束位置j,沒法知道起始位置i為多少啊 def maxSumDynamicProgramming(arr):# 本來是需要一個(gè)數(shù)組來記錄b的，然后找b[]里面的最大值# 但是我們得到一個(gè)b,就可以更顯最優(yōu)結(jié)果的，我只要記錄當(dāng)前最優(yōu)解就行了，所以只需要當(dāng)前的b# b的初值就是b[0-1]的值，也就是沒有元素時(shí)最大字段和為多少，為0cur_b =0# 用于記錄最優(yōu)的結(jié)果best_result = 0best_j = -1# 根據(jù)狀態(tài)方程自底向上完成for j in range(len(arr)):# b[j] = max{b[j-1]+arr[j],arr[j]}，當(dāng)b[j-1]>0為左邊，否則為右邊，也可以直接用maxif cur_b>0:cur_b += arr[j]else:cur_b = arr[j]# 每求出一個(gè)b,就更新一下當(dāng)前最優(yōu)解if cur_b >= best_result:best_result = cur_bbest_j = jreturn best_result,best_j總結(jié)
以上是生活随笔為你收集整理的算法优化：最大字段和，双指针遍历(n^2)，分治法(nlogn)，动态规划(n)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 分治法：BFPTR算法找第k小
- 下一篇： 算法优化：最大子段和，最大子矩阵和，一维