【題目鏈接】

洛谷 P1115 最大子段和

【題目考點(diǎn)】

1. 動(dòng)態(tài)規(guī)劃：線性動(dòng)規(guī)

• 最大子段和

【解題思路】

解法1：線性動(dòng)規(guī)

子段或子串指的是序列中連續(xù)的多個(gè)元素，子序列是指序列中可以不連續(xù)的多個(gè)元素。

1. 狀態(tài)定義

集合：所有子段
限制：子段所在區(qū)間范圍
屬性：加和
條件：最大
統(tǒng)計(jì)量：加和
狀態(tài)定義：dp[i]為以i為結(jié)尾的加和最大的子段的加和。

2. 狀態(tài)轉(zhuǎn)移方程

記a[i]為第i個(gè)元素的值
分割集合：考慮以第i元素為結(jié)尾的子段

• 子集1：第i元素自己作為一個(gè)子段，dp[i] = a[i]
• 子集2：如果第i元素和其左邊一些元素構(gòu)成子段，那么第i元素左邊的子段為以第i-1元素為結(jié)尾的子段，以第i-1元素為結(jié)尾的子段中加和最大的子段的加和為dp[i-1]，在這個(gè)子段后面添加第i元素，這個(gè)以i為結(jié)尾的子段加和為dp[i]=dp[i-1]+a[i]

以上二者取最大值。

3. 結(jié)果輸出

題目要求的是最大子段和，就是以每個(gè)位置為結(jié)尾的最大子段和中的最大值，即為求dp數(shù)組的最大值。

解法2：前綴和

求出原序列的前綴和，保存在s數(shù)組中。s[i]表示前i個(gè)數(shù)的和。
最大子段和即為：滿足j>i的s[j]-s[i]的最大值。
mi為數(shù)組s在下標(biāo)1~i中的最小值。那么s[i]-mi即為以i為結(jié)尾的子段的最大子段和。
最大子段和為以每個(gè)位置為結(jié)尾的最大子段和中的最大值。
i從1循環(huán)到n，不斷更新mi，保持mi為s[1]~s[i]中的最小值，求s[i]-mi的最大值。

解法3：雙指針

順序遍歷數(shù)組，當(dāng)前已經(jīng)選擇了以第i-1元素為結(jié)尾的子段，該子段和為s，看是否把第i個(gè)元素a[i]加入到子段中。

• 如果已有子段的和為負(fù)數(shù)，即s<0，那么s+a[i] < a[i]，也就是說第i元素自己作為一個(gè)子段的加和，要比將其接到前一個(gè)子段的末尾構(gòu)成的子段的加和要大。所以此時(shí)子段和應(yīng)該從s變?yōu)閍[i]
• 如果已有的子段和大于等于0， 即s>=0，那么s+a[i] >= a[i]，應(yīng)該將第i元素接到前一個(gè)子段的末尾，構(gòu)成以第i元素為結(jié)尾的子段，子段和從s變?yōu)閟+a[i]。

在遍歷過程中，求所有出現(xiàn)的子段和的最大值。

該算法實(shí)際是一種雙指針（尺取法）算法，子段的第一個(gè)元素的下標(biāo)為l，最后一個(gè)元素的下標(biāo)為r，當(dāng)前子段和為負(fù)數(shù)，則l改變，否則r改變。這里思考時(shí)借助了雙指針的思想，但代碼中并不需要寫出雙指針。

【題解代碼】

解法1：線性動(dòng)規(guī)

#include<bits/stdc++.h> using namespace std; #define N 200005 #define INF 0x3f3f3f3f int a[N], dp[N];//dp[i]:以i為結(jié)尾的加和最大的子段的加和 int main() {int n, mx = -INF;cin >> n;for(int i = 1; i <= n; ++i)cin >> a[i];for(int i = 1; i <= n; ++i)dp[i] = max(a[i], a[i] + dp[i-1]);for(int i = 1; i <= n; ++i)mx = max(mx, dp[i]);cout << mx;return 0; }

解法2：前綴和

#include<bits/stdc++.h> using namespace std; #define N 200005 #define INF 0x3f3f3f3f int a[N], s[N]; int main() {int n, mi = 0, mxSum = -INF;cin >> n;for(int i = 1; i <= n; ++i){cin >> a[i];s[i] = s[i-1] + a[i];}for(int i = 1; i <= n; ++i){mxSum = max(mxSum, s[i] - mi);mi = min(mi, s[i]);}cout << mxSum;return 0; }

解法3：雙指針

#include<bits/stdc++.h> using namespace std; #define N 200005 #define INF 0x3f3f3f3f int a[N], s; int main() {int n, mi = 0, mxSum = -INF;cin >> n;for(int i = 1; i <= n; ++i)cin >> a[i];for(int i = 1; i <= n; ++i){if(s < 0)s = a[i];elses += a[i];mxSum = max(mxSum, s);}cout << mxSum;return 0; }

總結(jié)

以上是生活随笔為你收集整理的洛谷 P1115 最大子段和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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