題目描述

HZ偶爾會(huì)拿些專業(yè)問題來忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)。今天測試組開完會(huì)后,他又發(fā)話了:在古老的一維模式識別中,常常需要計(jì)算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時(shí)候,問題很好解決。但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個(gè)負(fù)數(shù),并期望旁邊的正數(shù)會(huì)彌補(bǔ)它呢？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個(gè)開始,到第3個(gè)為止)。給一個(gè)數(shù)組，返回它的最大連續(xù)子序列的和，你會(huì)不會(huì)被他忽悠住？(子向量的長度至少是1)。

解題思路

方法一：動(dòng)態(tài)規(guī)劃。

狀態(tài)定義：定義dp[ i ]代表以元素nums[ i ]為結(jié)尾的連續(xù)子數(shù)組最大和。

轉(zhuǎn)移方程：若dp[ i-1 ]<=0，說明dp[ i-1 ]對dp[ i ]產(chǎn)生負(fù)貢獻(xiàn)，即 dp[ i-1 ] + nums[ i ]還不如nums[ i ]本身大。

• 當(dāng)dp[ i - 1 ] > 0時(shí)：執(zhí)行dp[ i ] = dp[ i - 1 ] + nums[ i ]；
• 當(dāng)dp[ i - 1 ] <= 0時(shí)：執(zhí)行dp[ i ] = nums[ i ]；

初始狀態(tài)：dp[0] = nums[0]，即以nums[0]結(jié)尾的連續(xù)子數(shù)組最大和為nums[0]。

時(shí)間復(fù)雜度：O(n)；空間復(fù)雜度：O(1)

源碼

public?class?Solution?{
????public?int?FindGreatestSumOfSubArray(int[]?array)?{
????????//動(dòng)態(tài)規(guī)劃
????????int?result?=?array[0];
????????
????????for(int?i?=?1;?i?????????????//array[i]表示前一個(gè)數(shù)對該數(shù)求和做正貢獻(xiàn)(保留)還是負(fù)貢獻(xiàn)(舍棄)
????????????array[i]?+=?Math.max(array[i?-?1],?0);
????????????
????????????//將目前得到的最大值與當(dāng)前取得的最大值進(jìn)行比較
????????????result?=?Math.max(result,?array[i]);
????????}
????????
????????return?result;
????}
}

運(yùn)行結(jié)果

總結(jié)

以上是生活随笔為你收集整理的最大连续子数组和 动态规划_剑指Offer算法题 33：连续子数组的最大和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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