最大連續(xù)和,也稱最大連續(xù)子段和。這個問題雖然簡單,但其中蘊含了很多算法的思想,包括動態(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)計算它的值,計算B(i,j)的值的時間花費為j-i+1,因此總的時間復(fù)雜度為

網(wǎng)友評論