題目描述

給定K個整數的序列{?N1,?N2,?...,?NK?}，其任意連續子序列可表示為{?Ni,?Ni+1,?...,?Nj?}，其中?1?<=?i?<=?j?<=?K。最大連續子序列是所有連續子序列中元素和最大的一個，例如給定序列{?-2,?11,?-4,?13,?-5,?-2?}，其最大連續子序列為{?11,?-4,?13?}，最大和為20。現在增加一個要求，即還需要輸出該子序列的第一個和最后一個元素。

輸入

測試輸入包含若干測試用例，每個測試用例占2行，第1行給出正整數K(?K<=?10000?)，第2行給出K個整數，中間用空格分隔，每個數的絕對值不超過100。當K為0時，輸入結束，該用例不被處理。

輸出

對每個測試用例，在1行里輸出最大和、最大連續子序列的第一個和最后一個元素，中間用空格分隔。如果最大連續子序列不唯一，則輸出序號i和j最小的那個（如輸入樣例的第2、3組）。若所有K個元素都是負數，則定義其最大和為0，輸出整個序列的首尾元素。

樣例輸入

5 -3 9 -2 5 -4 3 -2 -3 -1 0

樣例輸出

12 9 5 0 -2 -1

提示

?

?

這是一道稍微有點難度的動態規劃題。?

?

首先可以想到的做法是枚舉每個區間的和，預處理sum[i]來表示區間[1,?i]的和之后通過減法我們可以O(1)時間獲得區間[i,?j]的和，因此這個做法的時間復雜度為O(n^2)。?

?

然后這題的數據范圍較大，因此還需作進一步優化才可以AC。記第i個元素為a[i]，定義dp[i]表示以下標i結尾的區間的最大和，那么dp[i]的計算有2種選擇，一種是含有a[i-1]，一種是不含有a[i-1]，前者的最大值為dp[i-1]+a[i]，后者的最大值為a[i]。而兩者取舍的區別在于dp[i-1]是否大于0。

?

WA原因：答案錯誤50%，暫時還沒有排查出原因

#include <iostream> #include <algorithm> #include <vector>using namespace std; const int maxn = 10000; int A[maxn], dp[maxn]; //vector<int> p[maxn]; //記錄序列,pi表示以i結尾的序列 int k; int mx; int minusNum; int ans = 0;int main() {while(scanf("%d", &k) && k){fill(dp,dp+k,0); // for(int i = 0; i < k; i++) // { // p[i].clear(); // }minusNum = 0;for(int i = 0; i < k; i++){scanf("%d", &A[i]);if(A[i] < 0) minusNum++;}//所有k個元素都為負if(minusNum == k) printf("0 %d %d\n", A[0], A[k-1]);else{dp[0] = 0; // p[0].push_back(0);for(int i = 1; i < k; i++){if(dp[i-1] < 0) //只有A[i]一個元素{dp[i] = A[i]; // p[i].push_back(i);}else{ // p[i] = p[i-1]; // p[i].push_back(i);dp[i] = dp[i-1] + A[i];}}mx = 0;int ans1 = 0, ans2 = 0;int b1, b2;for(int i = 0; i < k; i++){if(dp[i] > dp[mx]){mx = i;}else if(dp[i] == dp[mx]){ // int ans1 = p[i][0] + p[i][p[i].size() - 1]; // int ans2 = p[mx][0] + p[mx][p[mx].size() - 1]; // if(ans1 > ans2) mx = i;if(dp[i] == A[i]){ans1 = A[i];}else{b1 = i;while(dp[b1] != 0){dp[b1--] -= A[b1];}ans1 = A[b1+1] + A[i];}if(dp[mx] == A[i]){ans2 = A[mx];}else{b2 = mx;while(dp[b2] != 0){dp[b2--] -= A[b2];}ans2 = A[b2+1] + A[mx];}if(ans1 < ans2) mx = i;}}printf("%d ", dp[mx]);if(dp[mx] == A[mx]){printf("%d\n", A[mx]);}else{ans = A[mx];while(dp[mx] != 0){dp[mx--] -= A[mx];}printf("%d %d\n", A[mx+1], ans);}}}return 0;}

?

總結

以上是生活随笔為你收集整理的Codeup-问题 A: 最大连续子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

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