51nod1050 循环数组最大子段和

思路：

分两种情况讨论。

实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 50005;
 5 ll sum[N];
 6 int main()
 7 {
 8     int n, x;
 9     while (cin >> n)
10     {
11         ll maxn = 0, minn = 0, ans = 0, mins = 0;
12         for (int i = 1; i <= n; i++)
13         {
14             cin >> x; sum[i] = sum[i - 1] + x;
15             ans = max(ans, sum[i] - minn);
16             mins = min(mins, sum[i] - maxn);
17             maxn = max(maxn, sum[i]); minn = min(minn, sum[i]);
18         }
19         ans = max(ans, sum[n] - mins);
20         cout << ans << endl;
21     }
22     return 0;
23 }