文章目錄

• • 題目分析
  • 題目鏈接

題目分析

來源：acwing

分析: dp題。

這道題糅合了兩個知識點：

dp求最值（區間之和）

動態求區間方案：區間之和相等的條件下：要求區間左端點最靠前，如果左端點相同，求區間右端點最靠前的方案。

第一題：dp求最值。

dp問題：狀態表示+狀態計算。

狀態表示： $f[i]$表示以i為右端點的區間和的最大值

狀態計算：

所以狀態轉移為
$f[i]=max(w_i,f[i?1]+w_i)$
化簡一下就是$f[i]=w_i+max(0,f[i?1])$

如果只有第一問，直接就用dp求出區間之和的最大值res。

int res =-1;for(int i =1, f =-1; i<=n; i++){if(f < 0) f = 0; //這一步就是 max(0, f(i-1))f += w[i];res = max(res, f);}cout <<res<<" ";

可是還得求出具體方案，那么需要對代碼進行加工：

第二題：求區間。

然后怎么求 左端點最靠前，右端點也最靠前的方案呢？ 當最優解區間是[i,j]的時候我們能找到嗎？下面是代碼

int res =-1; //區間和int l ,r; //左端點的值，右端點的值//f是臨時統計區間和//start臨時左端點下標for(int i =1, f =-1,start; i<=n; i++){//只有i左邊的區間和<0，才更新左端點startif(f<0) f =0 ,start =i;f += w[i];//區間和變大，則更新，主要更新右端點；if(res < f){res = f;l =w[start],r =w[i];}}

下面是解釋：
如果[i,j]是最優解區間，那么當我們走到i的時候，i前面的區間和必然是小于0的，否則最優解區間就不是[i,j]. 而是i前面某個值是左端點。所以當從左邊遍歷過來的時候，由于i左邊的區間和小于0，新的左端點就是i，即start = i。當左端點確定后，從i開始掃描的區間中，不存在區間和小于0一小段，這小段稱為前綴（如下圖，否則這段會被舍棄，最優解區間不是[i,j]），那么 右端點一直往右走更新。當ref ≥ f的時候，停止更新。這就是找左右端點的過程。

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 1e4+10;int n; int w[N];int main(){cin >> n;for(int i=1;i <=n; i++) cin >> w[i];int res = -1;//區間int l ,r;for(int i=1, f= -1 ,start; i <= n;i ++){//區間和小于0，就舍棄這個區間if(f<0) f = 0, start = i;f += w[i];if(res < f){res =f;//存的是值l =w[start] ,r =w[i];}}if(res < 0) res = 0 ,l=w[1],r =w[n];cout<<res<<" "<<l<<" "<<r;}

題目鏈接

PAT甲級1007 Maximum Subsequence Sum

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的PAT甲级1007 Maximum Subsequence Sum ：[C++题解]DP，最大子序列和、求最优的区间方案的全部內容，希望文章能夠幫你解決所遇到的問題。

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