环形最大M子段和，N个整数组成的序列排成一个环，a[1],a[2],a[3],…,a[n]（a[n-1], a[n], a[1]也可以算作1段），将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。

例如：-2 11 -4 13 -5 6 -1，分为2段，6 -1 -2 11一段，13一段，和为27。

 收起

 

输入

第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 100000)第2 - N+1行：N个整数 (-10^9 <= a[i] <= 10^9)

输出

输出这个最大和

输入样例

7 2-211-413-56-2

输出样例

26 相比v2，改成首尾相接的，如果首尾同号就归并。 代码：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;int n,m;ll d,last;ll s[100005];int l[100005],r[100005];int sc;void modify(int cur) {
     ///修改左右相邻结点的下标    int ll = l[cur],rr = r[cur];    r[ll] = rr;    l[rr] = ll;}int main() {    while(~scanf("%d%d",&n,&m)) {        sc = last = 0;        ll sum = 0,ans = 0,c = 0;        set
           
            
              > ss; for(int i = 0;i < n;i ++) { scanf("%lld",&d); if(d * last < 0) { s[++ sc] = sum; sum = d; } else sum += d; last = d; } if(sum) s[++ sc] = sum; if(s[1] > 0 && s[sc] > 0 || s[1] < 0 && s[sc] < 0) { s[1] += s[sc --]; } for(int i = 1;i <= sc;i ++) { ss.insert(make_pair(abs(s[i]),i)); c += s[i] > 0; ans += (s[i] > 0 ? s[i] : 0); l[i] = i - 1; r[i] = i + 1; } r[sc] = 1; l[1] = sc; while(c > m) { int cur = ss.begin() -> second; ss.erase(ss.begin()); ans -= abs(s[cur]); s[cur] += s[l[cur]] + s[r[cur]]; ss.erase(make_pair(abs(s[l[cur]]),l[cur])); modify(l[cur]); ss.erase(make_pair(abs(s[r[cur]]),r[cur])); modify(r[cur]); if(s[cur]) ss.insert(make_pair(abs(s[cur]),cur)); c --; } printf("%lld\n",ans); } return 0;}