美团笔试·回转寿司

小美邀请小团一同享用回转寿司。转盘上共有N盘寿司，排列成一个环形结构，其中第1盘与第2盘相邻，第2盘与第3盘相邻，依此类推，直至第N盘与第1盘相邻。小团对每盘寿司的美味程度有特定的评价，记作A[i]（该值可能为负数，表示小团对该盘寿司不感兴趣）。现在需要在转盘中选择一组连续的寿司盘，使得这些寿司的美味值总和达到最大（若不选任何寿司，则总和为0）。

输入：

首先输入一个整数T（1<=T<=10），代表测试数据的数量。
每组数据包含两行内容，第一行给出一个整数N（1<=N<=10^5）；
第二行输入N个由空格分隔的整数，分别表示A[1]至A[N]（-104<=A[i]<=104）。

输出：

对于每组输入数据，在单独的一行中输出一个整数，代表所选连续寿司美味值的最大总和。

输入示例

1
4
3 -2 4 -1

输出示例

6

最初考虑采用双重循环的方式进行计算，但这种方法会导致超时问题，在Python语言环境下无法运行。
进一步思考得出以下思路：可能的选择包括前缀和减去最小前缀和（可能是零或负数），以及前缀和加上以最后一个元素结尾的最大子数组和。

    #include<iostream>
    #inclu