最大子段和問題(編輯修改稿)
2024-08-15 19:15 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 max:=max+a[k]。 if maxans then ans:=max。 end。 write(ans)。 end. ① //不能不初始化或置為 0 ② //不能像排序一樣寫，單個(gè)數(shù)字也可以作為子段 注釋①： ①：答案初始化 Ans:=maxlongint。 這里不可以置為 0或是不初始化。最大字段和求解的數(shù)據(jù)中一定會(huì)有負(fù)數(shù)的數(shù)據(jù)（如果都是正數(shù)最大子段和就是所有數(shù)字相加），所以置為 0的錯(cuò)誤的初始化，比如下面的這種數(shù)字就過不了。 5 1 2 3 4 5 這個(gè)數(shù)據(jù)的最大子段和是 1（單個(gè) 1一段），但如果初始化為 0或不初始化答案就會(huì)是 0。 注釋②： ②：枚舉頭尾 for i:=1 to n do for j:=i to n do//這里不能用像排序的循環(huán)方式 ： for i:=1 to n1 do for j:=i+1 to n do 如果采用這樣的循環(huán)方式所求的最大子段和就不包括單個(gè)數(shù)字為一段的答案。對(duì)于以下這種數(shù)據(jù)會(huì)出現(xiàn)錯(cuò)誤。 5 1 2 3 4 5 這個(gè)數(shù)據(jù)的最大子段和是 1（單個(gè) 1一段）。但如果采用錯(cuò)用的循環(huán)方式所做出的答案就會(huì)是 1（ 1和 2）。 解法 (2)： 【算法概括】?jī)芍匮h(huán)枚舉 +預(yù)處理 【算法分析】雖然第一種解法最容易理解，但是效率非常低，而且有很多的和是重復(fù)計(jì)算過的。比如計(jì)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1