有兩種方式：

1.在首尾之間

2.在尾首之間

?

對(duì)于第一種直接來(lái)dp就好，第二種需要將其數(shù)組全部取負(fù)，然后取到其最大值（肯定是負(fù)數(shù)的最大值）然后dp即可，最后比較這兩個(gè)答案誰(shuí)比較大就輸出哪個(gè)

1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 #define max(a,b) a>b?a:b 5 6 const int maxn = 50000 + 5; 7 int a[maxn]; 8 int n; 9 long long dp[maxn]; 10 11 long long Sum(int a[]){ 12 dp[1] = a[1]; 13 long long ans = 0; 14 for (int i = 1; i <= n; i++){ 15 dp[i] = max(dp[i - 1] + a[i], a[i]); 16 ans = max(ans, dp[i]); 17 } 18 return ans; 19 } 20 21 int main(){ 22 ios::sync_with_stdio(false); 23 cin >> n; 24 long long sum = 0; 25 for (int i = 1; i <= n; i++){ 26 cin >> a[i]; 27 sum += a[i]; 28 } 29 long long ans1 = Sum(a); 30 for (int i = 1; i <= n; i++){ 31 a[i] = -a[i]; 32 } 33 long long ans2 = Sum(a); 34 long long Ans = max(ans1, ans2 + sum); 35 cout << Ans << endl; 36 37 return 0; 38 }

?

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

總結(jié)

以上是生活随笔為你收集整理的51Nod 1050 循环数组最大子段和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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