蒜厂年会|计蒜客2019蓝桥杯省赛 B 组模拟赛（一）

思路一：环形数组拆分成普通数组（通过搬运复制数据到尾部），再求前缀和，找出最大前缀和。因为枚举了每一个起点 所以最大连续和也一定出现在前缀和中！

思路二：

代码一：暴力，枚举数组的起点，环形数组通过把0~起点这段数据搬运到尾部，形成新的数组。再对新数组球前缀和，找出最大的前缀和即可。

#include<iostream>
using namespace std;

int n;
long long arr[20010];
long long s[20010];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    int maxtt = -1;
    int i;
    for(i = 1;i<=n;i++){
        //搬运数据
        for(int j=1;j<i;j++){ 
            arr[n+j] = arr[j];
        }
        int len = n + i;
        //求出最大的连续和(前缀和)
        s[i-1] = 0;
        for(int p = i;p<=len;p++){
            s[p] = s[p-1] + arr[p];
            if(s[p] > maxtt) maxtt = s[p];
        }
        
    }
    cout<<maxtt<<endl;
    return 0;   
} 

蒜厂年会|计蒜客2019蓝桥杯省赛 B 组模拟赛（一）

原文：https://www.cnblogs.com/fisherss/p/10346153.html