動態(tài)規(guī)劃法：

首先給一個任意的序列來說明這個問題

1 2 3 -1 -5 4 5 8

首先設(shè)一個dp數(shù)組，dp[i]表示前i個區(qū)間的最大子段和

如果dp[i-1] > 0，那么dp[i] = dp[i-1] + a[i]

否則dp[i] = a[i]

int max = 0; int b[n+1]; int start = 0; int end = 0; memset(b,0,n+1); for(int i = 1; i <= n; ++i) { if(b[i-1]>0) { b[i] = b[i-1]+a[i]; }else{ b[i] = a[i]; } if(b[i]>max) max = b[i]; }

?

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的最大子段和（动态规划及分治法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。