求最長總和序列，狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i-1]+a[i].a[i])

因?yàn)榭赡苡胸?fù)數(shù),所以要判斷dp是否大于0，如果小于0則序列中斷，從中斷點(diǎn)開始

起始點(diǎn)可以用數(shù)組s保存，有中斷點(diǎn)就保存，沒有的話s[i]=s[i-1]

另外還有輸出最后換行的問題，有時(shí)中間要換行但最后不需要換行，如果沒注意可能會(huì)出現(xiàn)PE

?

#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> using namespace std;#define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define debug printf("!\n") #define INF 10000 #define MAX(a,b) a>b?a:b #define blank pf("\n") #define LL long longint n; int dp[100010]; int a[100010]; int s[100010];int main() {int i,j,t,k;sf("%d",&t);for(k = 1;k<=t;){sf("%d",&n);mem(dp,0);mem(a,0);for(i = 0;i<n;i++){sf("%d",&a[i]);}dp[0]=a[0];int e=1;for(i = 1;i<n;i++){if(dp[i-1]>=0){dp[i] = max(dp[i-1]+a[i],a[i]);s[i] = s[i-1];}else{dp[i] = a[i];s[i] = i;}}int max = -1000;for(i=0;i<n;i++){if(max<dp[i]){max = dp[i];e=i;}}pf("Case %d:\n",k);pf("%d %d %d\n",max,s[e]+1,e+1);k++;if(k<=t)blank;} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/qlky/p/5155203.html

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

總結(jié)

以上是生活随笔為你收集整理的Max Sum（经典DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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