最大字段和問題雖然簡單，但蘊含了很多算法的思想，包括動態(tài)規(guī)劃和分治法。
問題描述
最大連續(xù)和問題 給出一個長度為n的序列A0,A1,...,An-1，求最大連續(xù)和。也就是，要求找到一組(i,j)滿足0≤i≤j≤n-1，使得Ai+Ai+1+...+Aj盡量大。
解法1 暴力枚舉
我們可以枚舉出所有的連續(xù)和，記B(i,j)=Ai+Ai+1+...+Aj，也就是 i 從0取到n-1，j 從 i 取到n-1。因此，我們要做的分為兩部分，第一部分是枚舉出所有的B(i,j)，第二部分是對于具體的B(i,j)計算它的值，那么時間復雜度
網(wǎng)友評論
