HDU 1003 Max Sum(AC代码)
2024-08-27 23:04:11
#include <stdio.h>
int main(){
int i,t,j,n,x;
int start,end,temp,max,sum;
scanf("%d",&t);
for(i=;i<t;i++){
temp=;
max=-;
sum=;
scanf("%d",&n);
for(j=;j<n;j++){
scanf("%d",&x);
sum+=x;
if(sum>=max){
max=sum;
start=temp;
end=j+;
}
if(sum<){
sum=;
temp=j+;
}
}
printf("Case %d:\n",i+);
printf("%d %d %d\n",max,start,end);
if(i!=t-){
printf("\n");
}
start=;
end=;
}
return ;
}
格式看代码就行啦。
情况分析:
1、序列全为负数,则找出最大的那个即可。
2、子序列前面(多个)为负数,后面为正数,则start一定在负数之后。
3、子序列后面(多个)为负数,前面为正数,则end一定在负数之前。
4、即所要求的子序列应是:第一个必须0或正数,最后一个必须为0或正数
解题分析:
1、start和end分别记下开始和结束。
2、sum计算自序列的总和,若总和大于最大值,则修改最大值
3、若出现过max,且sum一直在减少,则当sum小于0时,sum清零(此时前面出现过最大的序列,开始和结束已记好),sum是从temp处开始加起的,所以temp要保持和sum一致,即sum小于零时就要修改temp。
最新文章
- python之生成器
- struts2中的jsp值传到后台action接收的三种方法
- tomcat 虚拟主机配置
- Laravel不同数据库的模型之间关联
- javaScript中with的用法
- script标签的位置
- 安卓打开File Explorer里面不显示内容
- 【XSY2612】Comb Avoiding Trees 生成函数 多项式求逆 矩阵快速幂
- 描述各自页面的 page
- python web编程CGI
- 灯光探测器LightProbe[Unity]
- 存储过程打印超过8000的VARCHAR字符的问题
- 使用 Vue.js 结合bootstrap 实现的分页控件
- spring boot打jar包发布
- SSIS 学习之旅 FTP文件传输-脚本任务
- LeetCode 533----Lonely Pixel II
- Layui 弹出层组件——layer
- sublime text3配置ctrl+鼠标左键进行函数跳转【转】
- JavaScript:学习笔记(3)——正则表达式的应用
- FTP下载