题目
题意
- 给一个 n(1≤n≤1e5) 和长为 n 的数组 a(-30≤a[i]≤30)
- 设 b 为 a 的一个非空连续子数组
- 输出 sum(b)-max(b) 的最大值
思路
- 正解
- 从数组a的范围我们可以看出一点端倪
- 枚举 max(b)，把 > max(b) 的去掉，分裂出每个子段都求一遍最大子段和再减去枚举的 max(b)。
- 所有结果的最大值即为答案。
- 适用范围更广的（其实是为了贴板子）一种简单的最大连续子段板子O（N）
ini
复制代码
//b[j] = max{b[j - 1] + a[j],a[j]}, 1 <= j <= n int max_subsegment(int a[],int n){ int result = 0,b = 0; int begin = 0,end = 0;//记录最大子段的起始，终止下标 for(int i = 0; i < n;i++){ if(b > 0){ b += a[i]; }else{ b = a[i]; begin = i; } if(b > result){ result = b; end = i; } } return result; }
线段树分治板子O(logN)
scss
复制代码
struct node{ int l,r; int sum,ms;//maxsum int ml,mr;//maxl,maxr }tree[N*4]; void PushUp(int i) { tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; tree[i].ml=max(tree[i<<1].sum+tree[i<<1|1].ml,tree[i<<1].ml); tree[i].mr=max(tree[i<<1|1].sum+tree[i<<1].mr,tree[i<<1|1].mr); tree[i].ms=max(max(tree[i<<1].ms,tree[i<<1|1].ms),tree[i<<1].mr+tree[i<<1|1].ml); } void build(int i,int l,int r) { tree[i].l=l,tree[i].r=r; if(l==r) { tree[i].sum=tree[i].ml=tree[i].mr=tree[i].ms=a[l];//最小线段的值 return ; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); PushUp(i); } void update(int i,int pos,int val) { if(tree[i].l==tree[i].r) { tree[i].ms=tree[i].ml=tree[i].mr=tree[i].sum=val; return ; } int mid=(tree[i].l+tree[i].r)>>1; if(pos<=mid) update(i<<1,pos,val); else update(i<<1|1,pos,val); PushUp(i); } node query(int i,int l,int r) { if(l<=tree[i].l&&tree[i].r<=r) return tree[i]; int mid=(tree[i].l+tree[i].r)>>1; if(r<=mid) return query(i<<1,l,r); else if(l>mid) return query(i<<1|1,l,r); else { node x=query(i<<1,l,r),y=query(i<<1|1,l,r),res; //合并答案 res.sum=x.sum+y.sum; res.ml=max(x.sum+y.ml,x.ml); res.mr=max(y.sum+x.mr,y.mr); res.ms=max(max(x.ms,y.ms),x.mr+y.ml); return res; } }
- 回到题目上的做法
- 先利用单调栈找出以每个节点为最大值左边界和右边界(单调栈经典思路)
- 枚举所有点，用左边界和右边界之后，在这个区间内查询最大子段，和减当前这个点的值就是答案
- 注意，最大子段不一定包含这个最大值，看似逻辑上有bug，但是枚举了所有点，一定有枚举到正确的答案最大的情况
- 如果不包含这个最大值，但是减掉这个最大值，只会越小，不可能更新答案
- 所以这样的做法是正确的
代码
ini
复制代码
#include<bits/stdc++.h> #define debug1(a) cout<<#a<<'='<< a << endl; #define debug2(a,b) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<endl; #define debug3(a,b,c) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<endl; #define debug4(a,b,c,d) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<" "<<#d<<" = "<<d<<endl; #define debug5(a,b,c,d,e) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<" "<<#d<<" = "<<d<<" "<<#e<<" = "<<e<<endl; #define endl "\n" #define fi first #define se second #define int long long //#define int __int128 using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; typedef pair<LL,LL> PLL; //#pragma GCC optimize(3,"Ofast","inline") //#pragma GCC optimize(2) inline int rd() { int f=1,x=0;char c=getchar(); while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();} while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return f*x; } //常数定义 const double eps = 1e-4; const double PI = acos(-1.0); const int INF = 0x3f3f3f3f; const int N = 1e5+10; int a[N]; int L[N],R[N]; struct node{ int l,r; int sum,ms/*maxsum*/,ml,mr/*maxl,maxr*/; }tree[N*4]; void PushUp(int i) { tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; tree[i].ml=max(tree[i<<1].sum+tree[i<<1|1].ml,tree[i<<1].ml); tree[i].mr=max(tree[i<<1|1].sum+tree[i<<1].mr,tree[i<<1|1].mr); tree[i].ms=max(max(tree[i<<1].ms,tree[i<<1|1].ms),tree[i<<1].mr+tree[i<<1|1].ml); } void build(int i,int l,int r) { tree[i].l=l,tree[i].r=r; if(l==r) { tree[i].sum=tree[i].ml=tree[i].mr=tree[i].ms=a[l]; return ; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); PushUp(i); } void update(int i,int pos,int val) { if(tree[i].l==tree[i].r) { tree[i].ms=tree[i].ml=tree[i].mr=tree[i].sum=val; return ; } int mid=(tree[i].l+tree[i].r)>>1; if(pos<=mid) update(i<<1,pos,val); else update(i<<1|1,pos,val); PushUp(i); } node query(int i,int l,int r) { if(l<=tree[i].l&&tree[i].r<=r) return tree[i]; int mid=(tree[i].l+tree[i].r)>>1; if(r<=mid) return query(i<<1,l,r); else if(l>mid) return query(i<<1|1,l,r); else { node x=query(i<<1,l,r),y=query(i<<1|1,l,r),res; //合并答案 res.sum=x.sum+y.sum; res.ml=max(x.sum+y.ml,x.ml); res.mr=max(y.sum+x.mr,y.mr); res.ms=max(max(x.ms,y.ms),x.mr+y.ml); return res; } } void solve() { int n;cin >> n; a[0] = a[n+1] = 100; for(int i = 1;i <= n;i ++) { cin >> a[i]; } stack<int> sta; for(int i = 1;i <= n;i ++) { while(sta.size() && a[sta.top()] <= a[i]) { sta.pop(); } if(sta.empty()) L[i] = 1; else L[i] = sta.top() + 1; sta.push(i); } while(sta.size())sta.pop(); for(int i = n;i >= 1;i --) { while(sta.size() && a[sta.top()] <= a[i]) { sta.pop(); } if(sta.empty()) R[i] = n; else R[i] = sta.top() - 1; sta.push(i); } build(1,1,n); //for(int i = 1;i <= n ;i ++)update(1,i,a[i]); int ans = 0; for(int i = 1;i <= n ;i ++) { node now = query(1,L[i],R[i]); //debug4(i,L[i],R[i],now.ms); ans = max(ans,now.ms - a[i]); } //debug4(4,4,13,query(1,4,12).ms); cout << ans << endl; } signed main() { /* ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); */ int T = 1;//cin >> T; while(T--){ //puts(solve()?"YES":"NO"); solve(); } return 0; } /* */
