最大子段和問題-資料下載頁(yè)
2025-07-19 19:15本頁(yè)面
【正文】 )。 end. 解法 (3)： 【算法概括】動(dòng)態(tài)規(guī)劃求解 【算法分析】因?yàn)檫@一題是求連續(xù)的最大子段和， 階段最優(yōu)可以導(dǎo)致答案最優(yōu)，當(dāng)前最優(yōu)不會(huì)影響后面的計(jì)算，所以可以很自然地想到動(dòng)態(tài)規(guī)劃。如果前 i1個(gè)數(shù)的最大子段和小于零那么從第一個(gè)數(shù)到第i個(gè)數(shù)的最大子段和就是 a[i]，反之從第一個(gè)數(shù)到第i個(gè)數(shù)的最大子段和就是前 i1個(gè)數(shù)的最大字段和加a[i]。 【時(shí)間復(fù)雜度】 O(n) 可以支持 10000000以內(nèi)的數(shù)據(jù) 數(shù)據(jù)模擬： 用 f[i]來(lá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號(hào)-1