P1115 最大子段和 - 洛谷
題目描述
給出一個長度為?n?的序列?a，選出其中連續且非空的一段使得這段和最大。
輸入格式
第一行是一個整數，表示序列的長度?n。
第二行有?n?個整數，第?i?個整數表示序列的第?i?個數字?a?。
輸出格式
輸出一行一個整數表示答案。
輸入輸出樣例
輸入 #1
7
2 4 -3 -1 -2 -4 3輸出 #1
4說明/提示
樣例 1 解釋
選取?[3, 5]?子段?[3, -1, 2]，其和為?4。
數據規模與約定
- 對于 40% 的數據，保證?
n ≤ 2 × 103。 - 對于 100% 的數據，保證?
1 ≤ n ≤ 2 × 10?，-10? ≤ a? ≤ 10?。
思路：
遞歸，求出第i個為結尾的最長子數組的大小。
代碼：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N],mem[N];
int n;
int dfs(int x)
{int sum = -1e9;if(x < 0)return 0; elsereturn max(a[x],dfs(x-1)+a[x]);
}
int main(void)
{cin >> n;for(int i = 1 ; i <= n ; i++){cin >> a[i];}int ans = -1e9;for(int i = 1 ; i <= n ; i++){ans = max(ans,dfs(i));}cout << ans;return 0;} 
思路：
記憶化數組優化
代碼：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N],mem[N];
int n;
int dfs(int x)
{if(mem[x] != -1)return mem[x];int sum = -1e9;if(x < 0)return -1e9; elsesum = max(a[x],dfs(x-1)+a[x]);mem[x] = sum;return sum;
}
int main(void)
{cin >> n;memset(mem,-1,sizeof(mem));for(int i = 1 ; i <= n ; i++){cin >> a[i];}int ans = -1e9;for(int i = 1 ; i <= n ; i++){ans = max(ans,dfs(i));}cout << ans;return 0;} 
dp:
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N],dp[N];
int n;
int main(void)
{cin >> n;for(int i = 1 ; i <= n ; i++){cin >> a[i];}for(int i = 1 ; i <= n ; i++){dp[i] = max(a[i],dp[i-1] + a[i]);}int ans = -1e9; for(int i = 1 ; i <= n ; i++){ans = max(ans,dp[i]);}cout << ans;return 0;} 
貪心：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N],dp[N];
int n;
int main(void)
{cin >> n;for(int i = 1 ; i <= n ; i++){cin >> a[i];}int sum = 0,ans = -1e9;for(int i = 1 ; i <= n ; i++){if(sum < 0)sum = 0;sum += a[i];ans = max(ans,sum);}cout << ans;return 0;} 雙指針：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], n;
int main()
{cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}int maxsum = a[1];int currentsum = 0;int left = 1;// 右指針擴展窗口for (int right = 1; right <= n; right++) {currentsum += a[right]; // 累加當前元素到當前和maxsum = max(maxsum, currentsum); // 更新最大和while (currentsum < 0 && left <= right) // 舍棄負值子段 {currentsum -= a[left];left++;}}cout << maxsum << endl;return 0;
}
)
