【題目描述】

N個數圍成一圈，要求從中選擇若干個連續的數（注意每個數最多只能選一次）加起來，問能形成的最大的和。

【輸入描述】

第一行輸入N，表示數字的個數，第二行輸入這N個數字。

【輸出描述】

輸出最大和。

【樣例輸入】

8

2?-4?6?-1?-4?8?-1?3

【樣例輸出】

14

【數據范圍及提示】

1 <= N <= 100000，答案在Longint范圍內。

源代碼：#include<cstdio> #include<cstring> #include<algorithm> #define INF 100000000 using namespace std; int n,sum(0),i[100001],f[100001],ans=-INF,num=INF; int main() //當數據皆為負數時，什么都不會選，就是0，我覺得這樣應該也對。 {scanf("%d",&n);for (int a=1;a<=n;a++){scanf("%d",&i[a]);sum+=i[a]; //總和。 }for (int a=1;a<=n;a++) //1~n鏈狀時的最大值。 {if (f[a-1]>0)f[a]=f[a-1]+i[a];elsef[a]=i[a];ans=max(ans,f[a]);}memset(f,0,sizeof(f)); //別忘記初始化。for(int a=1;a<=n;a++) //環狀（區間在兩端）時的最大值。 {if (f[a-1]<0)f[a]=f[a-1]+i[a];elsef[a]=i[a];num=min(num,f[a]);}ans=max(ans,sum-num); //取其優。printf("%d",ans);return 0; }

?

轉載于:https://www.cnblogs.com/Ackermann/p/5709821.html

總結

以上是生活随笔為你收集整理的最大和的全部內容，希望文章能夠幫你解決所遇到的問題。

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