對于一個給定的長度為N的整數序列A，它的“子序列”的定義是：A中非空的一段連續的元素（整數）。你要完成的任務是，在所有可能的子序列中，找到一個子序列，該子序列中所有元素的和是最大的（跟其他所有子序列相比）。程序要求你輸出這個最大值。
輸入
輸入文件的第一行包含一個整數N，第二行包含N個整數，表示A。
其中
1 < = N < = 100000
-10000 < = A[i] < =　　10000
輸出
輸出僅包含一個整數，表示你算出的答案。
樣例輸入
5
3 -2 3 -5 4
樣例輸出
4

解題思路：
dp[i]表示以a[i]為結尾的序列的最大和，有兩種情況：
1.只有一個元素，則a[i]
2.有多個元素，則dp[i-1]+a[i]

所以關系表達式為：
dp[i] = max(dp[i-1]+a[i],a[i]);

初始化：
dp[0] = a[0];

代碼如下：

#include <iostream> using namespace std; const int N = 100010; int a[N]; int dp[N];int main() {int n;cin >> n;for (int i = 0; i < n; i++)cin >> a[i];dp[0] = a[0];for (int i = 1; i < n; i++) {dp[i] = max(dp[i - 1] + a[i], a[i]);}int res = -1e8;for (int i = 1; i < n; i++) {res = max(dp[i], res);}cout << res << endl;return 0; }

總結

以上是生活随笔為你收集整理的[蓝桥杯]最大连续子序列和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。