最大連續(xù)和，也稱最大連續(xù)子段和。這個(gè)問(wèn)題雖然簡(jiǎn)單，但其中蘊(yùn)含了很多算法的思想，包括動(dòng)態(tài)規(guī)劃和分治法。
問(wèn)題描述
最大連續(xù)和問(wèn)題 給出一個(gè)長(zhǎng)度為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)，第二部分是對(duì)于具體的B(i,j)計(jì)算它的值，計(jì)算B(i,j)的值的時(shí)間花費(fèi)為j-i+1，因此總的時(shí)間復(fù)雜度為
