51nod1049（最大子段和２）

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1049

题意：中文题诶～

思路：本题和51nod1049(题解)类似，不同的是本题的数列是一个环；

我们可以这样想，取得最大和的子段有两种情况：

　１．从第ｉ个元素到第j个元素，i<=j;　

　２．从第ｉ个元素到第j个元素，i>j;

第１种情况和1049那题是一样的；

第２种情况我们可以反过来想，所有元素的总和是固定的，若 i~j　能取到最大值，那么 j~i 的和为最小子段和，我们可以用和 1 中类似的方法求出最小子段和，再用所有元素的和减去它就能得到最大值啦；

两种情况取得的最大值中较大着即为答案；

代码：

 #include <bits/stdc++.h>

 #define ll long long

 using namespace std;

 const int MAXN=1e5+;

 ll a[MAXN], b[MAXN], c[MAXN];

 ll min(ll a, ll b){

     return a>b?b:a;

 }

 ll max(ll a, ll b){

     return a>b?a:b;

 }

 int main(void){

     ll n, ans=, mm=, mn=, x, num=, cnt=;

     cin >> n;

     for(int i=; i<=n; i++){

         cin >> x;

         ans+=x;

         a[i]=ans;

         if(ans>mm){

             b[i]=ans;

             mm=ans;

         }else{

             b[i]=b[i-];

         }

         if(ans<mn){

             c[i]=ans;

             mn=ans;

         }else{

             c[i]=c[i-];

         }

     }

     cout << endl;

     for(int i=; i<=n; i++){

         num=min(num, a[i]-b[i-]);

         cnt=max(cnt, a[i]-c[i-]);

     }

     ans=ans-num;

     cout << (ans>cnt?ans:cnt) << endl;

     return ;

 }

巴特西

51nod1049（最大子段和２）

最新文章

热门文章