当前位置:网站首页>HDU1231 最大连续子序列(分治or动规or双指针)
HDU1231 最大连续子序列(分治or动规or双指针)
2022-07-05 07:15:00 【Woodenman杜】
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1231
Question
Problem Description
给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ...,
Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个,
例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和
为20。
在今年的数据结构考卷中,要求编写程序得到最大和,现在增加一个要求,即还需要输出该
子序列的第一个和最后一个元素。
Input
测试输入包含若干测试用例,每个测试用例占2行,第1行给出正整数K( < 10000 ),第2行给出K个整数,中间用空格分隔。当K为0时,输入结束,该用例不被处理。
Output
对每个测试用例,在1行里输出最大和、最大连续子序列的第一个和最后一个元
素,中间用空格分隔。如果最大连续子序列不唯一,则输出序号i和j最小的那个(如输入样例的第2、3组)。若所有K个元素都是负数,则定义其最大和为0,输出整个序列的首尾元素。
Solve
这个题可以说非常经典了
暴力枚举左右界的做法就不说了,n^3哪哪都过不去,拿前缀和优化也不是一个好的做法。
动规
比较推荐的就是用动规、或者说双指针小模拟。但其实思路很简单
描述一下:
起初 l 和 r 都指向起点,然后 r 向右走,同时计算出 l 到 r 的和,如果加和是正数,那 r 就一直向右走,如果小于等于0,说明这一段加和不是想要的结果了(而且没有意义了),就让 l = r,重新开始计算加和,直到最后一个数被加和,期间不断更新最大和的结果 res
待会看代码吧,这鬼话我实在是说不清楚了
分治
以前听数据结构的时候讲分治用的也是这种题,我就说一下思路,代码不搞了:
所谓分治就是不断地把一个问题拆分成多个子问题去处理
对于这道题,我们先讨论一个状态:
从 l 到 r 的最大连续序列和,无非存在于 l 到 mid(mid = (l+r)/ 2) 或者 mid+1 到 r 之中,亦或者包含 mid ,左右都有,那我们就需要把三种情况的最大连续序列和都拿出来取最大值
先看左右都有的情况,怎么求呢,直接从 mid 分别向两边扩散去加和,什么时候停止呢,只能加到边界停止。
因为加了一个数和变小不代表之后不会变得比原来更大,所以只能是不断加,不断存最大值咯
再看最大连续序列和在两边的情况怎么办呢?
分治分治,分而治之,那就直接把序列拆成两半继续执行上述过程不就可以了,等拆到只剩一个元素的时候就是边界了,小于 0 的数就没有加和意义,正数就直接加上呗
伪代码写一下,因为我从来不相信自己的描述能力:
int solve(int l, int r)
{
//拆到只有一个元素的情况
if(l == r){
if(该元素 < 0) return 0;
else return 该元素;
}
int mid = (l + r) / 2;
//左界最大
int left = solve(l, mid);
//右界最大
int right = solve(mid + 1, r);
//包含中界
int l_num, r_num;
for mid to l
l_num = max(l_num, mid到l的元素和)
for mid to r
r_num = max(r_num, mid到r的元素和)
//取最大值返回
return max(l_num + r_num, left, right);
}
AC Code
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 10000
using namespace std;
int n, a[N+1];
int main(void)
{
while(~scanf("%d", &n))
{
if(n == 0) break; //运行结束判断
bool ans = false; //全负数判别
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
if(a[i] >= 0) ans = true;
}
if(!ans){ //全为负数
cout <<0 <<" " <<a[1] <<" " <<a[n] <<endl;
continue;
}
//结果计算
int l, r, resl, resr, res = -1e9, dp = 0;
l = r = resl = resr = 1;
for(int i = 1; i <= n; i++){
if(dp > 0){ //元素和大于0,直接添加元素
dp += a[i];
r++;
}else{ //元素和小于等于0,按0添加元素
dp = a[i];
l = r = i; //更新左右边界
}
if(dp > res){
res = dp; //更新最大值
resl = l; resr = r; //更新左右界
}
}
cout <<res <<" " <<a[resl] <<" " <<a[resr] <<endl;
}
return 0;
}
边栏推荐
- Delayqueue usage and scenarios of delay queue
- ORACLE CREATE SEQUENCE,ALTER SEQUENCE,DROP SEQUENCE
- 【软件测试】02 -- 软件缺陷管理
- ROS2——安装ROS2(三)
- [solved] there is something wrong with the image
- PowerManagerService(一)— 初始化
- PHY驱动调试之 --- PHY控制器驱动(二)
- Error: "mountvolume.setup failed for volume PVC fault handling
- 数学分析_笔记_第8章:重积分
- Mid 2022 documentary -- the experience of an ordinary person
猜你喜欢
Solve tensorfow GPU modulenotfounderror: no module named 'tensorflow_ core. estimator‘
[vscode] prohibit the pylance plug-in from automatically adding import
Delayqueue usage and scenarios of delay queue
PHY drive commissioning --- mdio/mdc interface Clause 22 and 45 (I)
Negative number storage and type conversion in programs
SD_ CMD_ SEND_ SHIFT_ REGISTER
Concurrent programming - how to interrupt / stop a running thread?
C learning notes
【软件测试】06 -- 软件测试的基本流程
Steps and FAQs of connecting windows Navicat to Alibaba cloud server MySQL
随机推荐
ROS2——常用命令行(四)
氢氧化钠是什么?
[tf1] save and load parameters
Now there are HTML files and MVC made with vs (connected to the database). How can they be connected?
PowerManagerService(一)— 初始化
第 2 章:小试牛刀,实现一个简单的Bean容器
*P++, (*p) + +, * (p++) differences
Qu'est - ce que l'hydroxyde de sodium?
Negative number storage and type conversion in programs
2022年中纪实 -- 一个普通人的经历
M2DGR 多源多场景 地面机器人SLAM数据集
PHY drive commissioning --- mdio/mdc interface Clause 22 and 45 (I)
[software testing] 02 -- software defect management
DelayQueue延迟队列的使用和场景
基于FPGA的一维卷积神经网络CNN的实现(八)激活层实现
[idea] efficient plug-in save actions to improve your work efficiency
The difference between NPM install -g/-save/-save-dev
ROS2——Service服务(九)
About vscode, "code unreachable" will be displayed when calling sendline series functions with pwntools“
[OBS] x264 Code: "buffer_size“