給定由n個(gè)整數(shù)（其中可能有負(fù)數(shù)）組成的序列a1，a2，...an，求該序列形如
的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為0。依此定義，所求的最優(yōu)值為：
動(dòng)態(tài)規(guī)劃解決方案：記
，則對(duì)于n個(gè)整數(shù)序列的最大子段和問(wèn)題，
即為所求。
動(dòng)態(tài)規(guī)劃遞歸式：
問(wèn)：對(duì)于實(shí)例：（a1，a2，...a6）＝（－2，11，－4，13，－5，－2）按照前述動(dòng)態(tài)規(guī)劃遞歸式填充b數(shù)組，算法運(yùn)行完畢后，請(qǐng)寫出b數(shù)組中的數(shù)值，和最大子段和的值。
您可能感興趣的試卷
你可能感興趣的試題
最新試題
使用窮舉法求解最長(zhǎng)遞增子序列的時(shí)間復(fù)雜度為（）。
舍伍德算法思想是通過(guò)引入隨機(jī)化策略將確定性算法改造為隨機(jī)算法，打破原來(lái)確定性算法在某些實(shí)例情況下，其時(shí)間復(fù)雜性必然遠(yuǎn)高于平均時(shí)間復(fù)雜性的規(guī)律。下面哪些算法可以應(yīng)用舍伍德算法思想？（）
輸入數(shù)組（-1，0，1，-2，3），它的最大子段和是（）。
0-1背包問(wèn)題與部分背包問(wèn)題的區(qū)別在于（）。
在使用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同，即將一個(gè)問(wèn)題分成大小相等的多個(gè)子問(wèn)題的處理方法是行之有效的。
Prim算法適合稀疏圖，其時(shí)間復(fù)雜度只與邊的數(shù)目有關(guān)。
用漸進(jìn)表示法分析算法復(fù)雜度的增長(zhǎng)趨勢(shì)。
?優(yōu)先隊(duì)列式分支限界法解決0-1背包問(wèn)題時(shí)，下面描述正確的是（）。
在一個(gè)至少包含三個(gè)頂點(diǎn)的加權(quán)連通單向圖中，假定邊的權(quán)重互不相同，則權(quán)重最大的邊不可能被包含在任何最小生成樹(shù)中。
在N皇后問(wèn)題中，需要將棋盤當(dāng)做一個(gè)二維數(shù)組來(lái)分析，對(duì)于該二維數(shù)組，以下說(shuō)法正確的是（）。