最大子段和
題目描述
給出一個(gè)長(zhǎng)度為 n n n 的序列 a a a，選出其中連續(xù)且非空的一段使得這段和最大。
輸入格式
第一行是一個(gè)整數(shù)，表示序列的長(zhǎng)度 n n n。
第二行有 n n n 個(gè)整數(shù)，第 i i i 個(gè)整數(shù)表示序列的第 i i i 個(gè)數(shù)字 a i a_i ai?。
輸出格式
輸出一行一個(gè)整數(shù)表示答案。
樣例 #1
樣例輸入 #1
7
2 -4 3 -1 2 -4 3
樣例輸出 #1
4
提示
樣例 1 解釋
選取 [ 3 , 5 ] [3, 5] [3,5] 子段 { 3 , ? 1 , 2 } \{3, -1, 2\} {3,?1,2}，其和為 4 4 4。
數(shù)據(jù)規(guī)模與約定
- 對(duì)于 40 % 40\% 40% 的數(shù)據(jù)，保證 n ≤ 2 × 1 0 3 n \leq 2 \times 10^3 n≤2×103。
- 對(duì)于 100 % 100\% 100% 的數(shù)據(jù)，保證 1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105， ? 1 0 4 ≤ a i ≤ 1 0 4 -10^4 \leq a_i \leq 10^4 ?104≤ai?≤104。
題解
這是一道經(jīng)典的動(dòng)態(tài)規(guī)劃，解決這個(gè)題首先要找到狀態(tài)轉(zhuǎn)移方程。
最大子段和，首先這個(gè)起始位置不能為負(fù)數(shù)，如果只有一個(gè)數(shù)，那么最大子段只能說負(fù)數(shù)，如果不是，且有正數(shù)存在的情況，那么起始值肯定不是負(fù)數(shù)，初始值我們讓他等于第一個(gè)值。定義dp數(shù)組，記錄的是當(dāng)前位置子段最大和，那么這是什么意思呢，在第一個(gè)數(shù)輸進(jìn)來之后，第二個(gè)數(shù)輸進(jìn)來，我們就開始比較，如果前面dp加上當(dāng)前輸入這個(gè)數(shù)比當(dāng)前單獨(dú)這個(gè)數(shù)小的話，很明顯，前面的數(shù)據(jù)我們不需要了，那么就是需要當(dāng)前這個(gè)數(shù)，并且以他開始，所以我們此時(shí)的dp就是輸入的數(shù)，后續(xù)的一直這樣比較。
這個(gè)狀態(tài)轉(zhuǎn)移方成就是 d p [ i ] = m a x ( d p [ i ? 1 ] + a [ i ] , a [ i ] ) dp[i] = max(dp[i-1]+a[i],a[i]) dp[i]=max(dp[i?1]+a[i],a[i])
在我們進(jìn)行上述比較的同時(shí)，我們需要注意一點(diǎn)那就是dp[n]并不一定是最大值，下面我們看一個(gè)例子5 200 200 -888 1 1 ，如果我們直接輸出dp[n]那么就是2，很明顯最大值是dp[3] 是 405，所以我們?cè)俦闅v時(shí)候，就需要考慮定義一個(gè)最大值max 即我下面代碼里的res，初始值為-10000，因?yàn)轭}目里說明 ? 1 0 4 ≤ a i ≤ 1 0 4 -10^4 \leq a_i \leq 10^4 ?104≤ai?≤104，那么他最小也只是-1000，設(shè)置為-10000的話，第一個(gè)數(shù)進(jìn)來最大值就是第一個(gè)數(shù)。文章來源：http://www.zghlxwxcb.cn/news/detail-740954.html
#include <bits/stdc++.h>
using namespace std;
int n,res = -100000,dp[200001]={0},a[200001];
int main()
{
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
dp[i] = max(dp[i-1]+a[i],a[i]);
res = res>dp[i]?res:dp[i];
}
cout << res;
return 0;
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-740954.html
到了這里，關(guān)于最大子段和（動(dòng)態(tài)規(guī)劃詳細(xì)解析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
