首页 > 其他分享 >P1121 环状最大两段子段和

P1121 环状最大两段子段和

时间:2023-06-09 09:03:20浏览次数:37  
标签:ba int max 段子 P1121 环状 两子 最大

P1121 环状最大两段子段和

非环状最大两子段和

\[fr[i]表示第1 \to i个元素的最大子段和 ba[i]表示第n \to i个元素的最大子段和 所以最大两子段和就是max(fr[i]+ba[i+1]),i \in [1,n) \]

int Solve(){
	int ans=-0x3f3f3f3f;
	
	for(int i=1;i<=n;i++) fr[i]=max(fr[i-1],0ll)+a[i];
	for(int i=1;i<=n;i++) fr[i]=max(fr[i],fr[i-1]);
	
	for(int i=n;i>=1;i--) ba[i]=max(ba[i+1],0ll)+a[i];
	for(int i=n;i>=1;i--) ba[i]=max(ba[i],ba[i+1]);
	
	for(int i=1;i<n;i++)
		ans=max(ans,fr[i]+ba[i+1]);
		
	return ans;
}

环状最大两子段和

  • 求非环状最大两子段和 \(ans1\),再求非环状最小两子段和 \(ans2\),这样两个最小子段和能把环分成两部分,就是环状最大两子段和\(sum+ans2(负)\),与非环状最大两子段和取最大值即可

  • 求非环状最小两子段和,其实就是求原序列的相反数的非环状最大两子段和,但是如果序列中只有一个正数会导致所求的非环状最大两子段相连,只将序列分为一部分,所以如果序列中只有一个正数,那么答案就是非环状最大两子段和‘

  • 如果序列中全为负数,那么原序列的相反数的非环状最大两子段和会等于原序列和的相反数,导致\(sum+ans2=0\),无效,所以答案就是\(ans1\)

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;

int n;
int a[N],fr[N],ba[N];
int sum,cnt,ans1,ans2;

int Solve(){
	int ans=-0x3f3f3f3f;
	
	for(int i=1;i<=n;i++) fr[i]=max(fr[i-1],0ll)+a[i];
	for(int i=1;i<=n;i++) fr[i]=max(fr[i],fr[i-1]);
	
	for(int i=n;i>=1;i--) ba[i]=max(ba[i+1],0ll)+a[i];
	for(int i=n;i>=1;i--) ba[i]=max(ba[i],ba[i+1]);
	
	for(int i=1;i<n;i++)
		ans=max(ans,fr[i]+ba[i+1]);
		
	return ans;
}

signed main(){
	freopen("1.in","r",stdin);
	memset(fr,-0x3f3f3f3f,sizeof(fr));
	memset(ba,-0x3f3f3f3f,sizeof(ba));
	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
		if(a[i]>0) cnt++;
	}
	
	ans1=Solve();
	if(cnt==1){
		cout<<ans1<<"\n";
	}else{
		memset(fr,-0x3f3f3f3f,sizeof(fr));
		memset(ba,-0x3f3f3f3f,sizeof(ba));
					
		for(int i=1;i<=n;i++)
			a[i]=-a[i];
		ans2=sum+Solve();
		if(!ans2) ans2=-0x3f3f3f3f;
		cout<<max(ans1,ans2)<<"\n";
	}
}

标签:ba,int,max,段子,P1121,环状,两子,最大
From: https://www.cnblogs.com/wangyangjena/p/17468149.html

相关文章

  • 用环状天线测向电压表鉴相器电路定位的无线电测向仪
    用环状天线测向电压表鉴相器电路定位的无线电测向仪用环状天线测向电压表鉴相器电路定位的无线电测向仪,是通过相互垂直的两个环状天线接收远处高频信号发生器发出的信号,来实现测量信号发生器方向的仪器。当环状天线面向高频信号发生器的方向时,它接收的信号强度最大,当环状天线偏移高......
  • 环状替换法详解
    环状替换法详解给定一个整数数组nums,将数组中的元素向右轮转k个位置,其中k是非负数。链接:https://leetcode.cn/problems/rotate-array示例:输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,7,1,2,3,4]解释:向右轮转1步:[7,1,2,3,4,5,6]向右轮转2步:[6,7,1,2,3,4,......
  • P1121
    #include<bits/stdc++.h>usingnamespacestd;constintmaxn=206;intn[maxn],m[maxn],ans[maxn];intmain(intargc,charconst*argv[]){stringa,b;while(cin>>a>>b){for(inti=0;i<maxn;i++)ans[i]=0;intl......
  • chatgpt回答了几个关于程序员的段子
    1.一个程序员被问到什么是压缩,他回答:“就是将10个字符压缩成9个字符。”2.为什么程序员总是把自己当作0和1?因为他们觉得自己是二进制最好的。3.什么是程序员最喜欢......
  • 环状图,三种渐变
    <template><div:style="{width:width,height:height}"ref="donutChart"></div></template><script>constecharts=require('echarts');exportdefault{name:"......
  • 搞笑段子
    1某年秋天,和男朋友刚相处没多久,临时决定去海边。我只穿了件卫衣,男朋友穿了外套和里面是很厚的衬衫。去海边的路上他热了,就把外套搭在手上。到了海边,海风一吹我就觉得凉飕......
  • [数据分析与可视化] 数据绘图要点8-环状条形图的使用
    date:2021-12-2911:46:41+0800tags:-数据分析与可视化-R语言数据绘图要点8-环状条形图的使用环状条形图RADIALBARCHARTS是指用极坐标而不是笛卡尔平面绘......
  • [R语言] 基于R语言实现环状条形图的绘制
    环状条形图(Circularbarplot)是条形图的变体,图如其名,环状条形图在视觉上很吸引人,但也必须小心使用,因为环状条形图使用的是极坐标系而不是笛卡尔坐标系,每一个类别不共享相同......
  • Python爬虫采集搞笑段子示例
    对于爬虫的用处不同的人有不同的看法,对于我而言,他是一门技能也是一门艺术,只有掌握其中的原理,才能让你体会到真正的快乐。下文就是我用python爬虫爬取搞笑段子的实例可以一起......
  • 拓端tecdat|R语言谱聚类、K-means聚类分析非线性环状数据比较
    有些问题是线性的,但有些问题是非线性的。我假设,你过去的知识是从讨论和解决线性问题开始的,这是一个自然的起点。对于非线性问题的解决,往往涉及一个初始处理步骤。这个初始......