最大子段和問題-資料下載頁
2025-07-19 19:15本頁面
【正文】 )。 end. 解法 (3)： 【算法概括】動態(tài)規(guī)劃求解 【算法分析】因為這一題是求連續(xù)的最大子段和， 階段最優(yōu)可以導致答案最優(yōu)，當前最優(yōu)不會影響后面的計算，所以可以很自然地想到動態(tài)規(guī)劃。如果前 i1個數(shù)的最大子段和小于零那么從第一個數(shù)到第i個數(shù)的最大子段和就是 a[i]，反之從第一個數(shù)到第i個數(shù)的最大子段和就是前 i1個數(shù)的最大字段和加a[i]。 【時間復雜度】 O(n) 可以支持 10000000以內(nèi)的數(shù)據(jù) 數(shù)據(jù)模擬： 用 f[i]來表示以 a[i]結(jié)尾的最大子段和 f[1] f[2] f[3] f[4] f[5] 5 1 2 3 2 3 f 1 1 3 1 4 代碼： var n,i,j,ans:longint。 a,f:array[0..100]of longint。 begin read(n)。 for i:=1 to n do read(a[i])。 ans:=maxlongint。 for i:=1 to n do begin if a[i]+f[i1]a[i] then f[i]:=a[i]+f[i1] else f[i]:=a[i]。 If f[i]ans then ans:=f[i] end。 write(ans)。 end. 謝謝！
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1