描述
小美请小团吃回转寿司。转盘上有N盘寿司围成一圈，第1盘与第2盘相邻，第2盘与第3盘相邻，…，第N-1盘与第N盘相邻，第N盘与第1盘相邻。小团认为第i盘寿司的美味值为A[i]（可能是负值，如果小团讨厌这盘寿司）。现在，小团要在转盘上选出连续的若干盘寿司，使得这些寿司的美味值之和最大（允许不选任何寿司，此时美味值总和为0）。
输入描述:
第一行输入一个整数T（1<=T<=10），表示数据组数。
每组数据占两行，第一行输入一个整数N（1<=N<=10^5）；
第二行输入N个由空格隔开的整数，表示A[1]到A[N]（-10^4 <=A[i]<= 10^4）。
输出描述:
每组数据输出占一行，输出一个整数，表示连续若干盘寿司的美味值之和的最大值。
答案及解析
题目要求环形数组的连续子数组的最大和，我们先不要去管数组是环形的情况，利用动态规划求解连续子数组的最大和以及最小和。
(1) 不考虑环形得到的最大值：题中允许寿司首尾相连的环形数组情况，因此常规求得的连续子数组的最大和就是我们排除这种情况之外的所有情况中的最大和。
(2) 只考虑环形得到的最大值：而对于首尾相连的情况，我们可以这样考虑，如果常规求得的连续子数组的和达到了最小，那么总和减去这个最小值就等于首尾相连情况的最大值了。
此为本题解题关键。
代码实现
```c++
class Cake()
{
int t;
while ( cin >> t )
{
for ( auto i = 0; i < t; ++i )
{
int minNum = INT_MIN;
int maxNum = INT_MAX;
int total = 0;
int n;
cin >> n;
vector
for ( auto j = 0; j < n; ++j )
{
int x;
cin >> x;
v.push_back(x);
}
vector
vector
dpMax[0] = dpMin[0] = v[0];
for ( auto i = 1; i < n; ++i )
{
total += v[i];
dpMax[i] = max(dpMax[i - 1] + v[i], v[i]);
dpMin[i] = max(dpMin[i - 1] + v[i], v[i]);
if ( maxNum < dpMax[i] )
maxNum = dpMax[i];
if ( minNum > dpMin[i] )
minNum = dpMin[i];
}
cout << max(maxNum, total - minNum) << endl;
}
}
}
