算法笔记

1.非连续最大子段和

如果不全为负数，最大子段和所有大于等于0的元素的和；如果全为负数，最大子段和为最大的负数。

2.连续最大子段和

①无长度限制：

例题：

代码：

#include
      
       using namespace std;#define ll long longint main(){    ios::sync_with_stdio(false);    int n;    ll ans=1ll<<63,now=0;    cin>>n;    while(n--)    {        int a;        cin>>a;        now+=a;        if(now>ans)ans=now;        if(now<0)now=0;    }    cout<
       
        <
       
      

代码：

#include
      
       using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int INF=0x3f3f3f3f;int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int T,a,n;    while(cin>>T)    {        for(int i=1;i<=T;i++)        {            cin>>n;            int l,r,_l=1,mx=-INF,sum=0;            for(int j=1;j<=n;j++)            {                cin>>a;                sum+=a;                if(sum>mx)                {                    mx=sum;                    l=_l;                    r=j;                }                if(sum<0)                {                    sum=0;                    _l=j+1;                }            }            if(i-1!=0)cout<
      

②有长度限制（如最大连续奇数字段和）

代码：

#include
      
       using namespace std;const int N=1e5+5;int a[N];int main(){    int t;    cin>>t;    while(t--)    {        int n;        cin>>n;        for(int i=0;i
       
        >a[i];        int sum=a[0],ans=a[0];        for(int i=1;i