CF1359D Yet Another Yet Another Task [ dp ]

D. Yet Another Yet Another Task

题意：一个数列，找字段和去除段内最大值后最大的区间；

枚举最大值 _max，对于有比 _max 大的区间都不考虑，在此基础上求最大字段和

int n,a[MAX],ans=0;
int main(){
	//freopen("in","r",stdin);
	sf(n);
	fi(i,0,n) sf(a[i]);
	fi(_max,1,31){
		int em=0,res=0;
		fi(i,0,n){
			int tmp= a[i]>_max?-INF:a[i];
			em=max(em,0)+tmp;
			res=max(res,em);
		}
		ans = max(ans,res-_max);
	}
	pfn(ans);
	return 0;
}