题解 | #环形数组的连续子数组最大和#

解题思路1：

• 看似明显的线性dp
• 但是对于每一个点作为起点做dp无疑是暴力解法。时间复杂度在$O(N^2)O(N^2)$,结果可想而知超时

#include<bits/stdc++.h>//超时的代码
using namespace std;
int solve(int n, vector<int> &v, vector<int> &dp);
int process2(int start, vector<int>&v);
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i){
        scanf("%d",&v[i]);
    }
    vector<int> dp(n, INT_MIN);
    cout<<solve(n,v, dp)<<endl;
    return 0;
}
int solve(int n, vector<int> &v, vector<int> &dp){
    int ans = process2(0, v);
    for(int i = 1; i < n; ++i){
        ans = max(ans,process2(i,v));
    }
    return ans;
}
int process2(int start, vector<int>&v){
    int ans = v[start];
    for(int i = 1; i < v.size(); ++i){
        ans = max(ans+v[(start + i)%v.size()],v[(start+i)%v.size()]);
    }
    return ans;
}

解题思路2：

• 切换看法，按照普通最大连续和的思路，即在dp的过程中可以得到最大的连续子数组和。
• 同理，如果再求一个最小的连续子数组和，就会发现一个特性。
• 假设用sum记录整个数组的和，那么最大连续子数组和dpmax 和最小连续子数组dpmin和一定是相连的两部分，因为假设不想连，中间这一段要么大于0，那么它应该属于最大子数组连续和，否则它应该属于最小连续子数组和。
• 故最后求得sum，dpmax，dpmin以后就可以进行判定。假设这说明数组两边的端点只和是正值，故应该把这一部分留给dpmax$(dpmax=sum-dpmin)(dpmax\; =\; sum\; -\; dpmin)$，否则直接返回dpmax即可，当然这里有一个特例（在初始化dpmax的时候给予了数组的第一个值$v[0]v[0]$，如果其是负数，则必定有 故此处应该特判，如果直接返回即可）

#include<bits/stdc++.h>
using namespace std;
int solve(vector<int> &v){
    int sum, dpmx, dpmn, mx, mn;
    dpmx = dpmn = mx = mn = sum = v[0];
    for(int i = 1; i < v.size(); ++i){
        mx = max(mx + v[i], v[i]);
        mn = min(mn + v[i], v[i]);
        dpmx = max(dpmx, mx);
        dpmn = min(dpmn, mn);
        sum += v[i];
    }
    if(dpmx< 0) return dpmx;
    if (dpmx + dpmn < sum) dpmx = sum - dpmn;
    return dpmx;
}
int main(){
    int n;
    cin >>n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i){
        cin>>v[i];
    }
    cout<<solve(v)<<endl;
    return 0;
}