文档章节

求连续向量的最大子和问题(扫描算法)

huser_YJ
 huser_YJ
发布于 2014/09/22 16:38
字数 749
阅读 20
收藏 0

问题来自《编程珠玑》这本书,我记得以前考研的时候模拟题目中也有过类似的题目,当时书上的代码特别简单易懂,不过也有些时日了,当时是怎样写的基本也就忘了。

现在回过头来在看看这个问题。


1.  问题描述

问题来自一维的模式识别,问题的输入是具有n个浮点数的向量x,输出是输入向量的任何连续子向量的最大和。例如,如果输入向量包含下面10个元素:

31

-41

59

26

-53

58

97

-93

-23

84

那么该程序的输出为x[2..6]的总和,即187。当所有数都是正数时,问题很容易解决,此时最大的子向量就是整个输入向量。当输入中含有负数时麻烦就来了:是否应该包含某个负数并期望旁边的整数会弥补它呢?

2.  简单算法

完成该任务的浅显程序就是对所有满足0<=i<=j<n的(i,j)整数对进行迭代。对每个整数对,程序都要计算x[ij]的总和,并检验总和是否大于迄今为止的最大总和。该算法的伪代码如下所示:

maxsofar = 0

for i = [0,n)

     for j = [i,n)

         sum = 0

         for k = [i,j]

              sum += x[k]

              /* sum is sum of x[i..j] */

              maxsofar = max(maxsofar, sum)

     这段代码简洁、直观并且易于理解。不幸的是,程序的运行速度也很慢。

3.  两个平方算法

有两个算法可以明显地提高第一个算法的速度,其中一个是比较明显可想的,而另外一个则不那么明显,它们的时间复杂度都是平方时间(对于输入规模n来说,需要执行O(n^2 )步)。

可以注意到,x[i..j]的总和与前面已计算出的总和(x[i..j-1]的总和)密切相关。利用这一关系即可得到算法。伪码如下:

maxsofar = 0

for i = [0,n)

     sum = 0

     for j = [i,n)

         sum += x[j]

         /* sum is sum of x[i..j] */

          maxsofar = max(maxsofar, sum)

     另一个平方算法是通过访问在外循环执行之前就已构建的数据结构的方式在内循环中计算总和。cumarr中的第i个元素包含x[0..i]中各个数的累加和,所以x[i..j]中各个数的总和可以通过计算cumarr[j]-cumarr[i-1]得到。从而得到如下所示的伪码:

cumarr[-1] = 0

for i = [0,n)

     cumarr[i] = cumarr[i-1] + x[i]

maxsofar = 0

for i = [0,n)

     for j = [i,n)

     sum = cumarr[j] - cumarr[i-1]

     /* sum is sum of x[i..j] */

     maxsofar = max(maxsofar, sum)

下面开始贴上代码

#include<stdio.h>

void main()
{
	int i,end_max,sum;
	int a[10]={31,-41,59,26,-93,58,97,-93,-23,84};

	
	end_max=a[0];
	sum=0;
	for(i=1;i<10;i++)
	{

		if(end_max>0)
		{
			if(end_max>sum)
				sum=end_max;
			end_max+=a[i];
		}
		else 
			end_max=a[i];
	}
	
	printf("%d",sum);
}


© 著作权归作者所有

huser_YJ
粉丝 2
博文 21
码字总数 28816
作品 0
武汉
私信 提问
给定一个整数数组(有正数有负数),找出总和最大的连续数列,并返回总和。

一、什么是求最大连续子数列和 首先来看看这是个怎样的问题的,问题描述:一个整型数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和,求所有子...

一贱书生
2016/11/26
800
0
Algo-Practice: 算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

记录一些算法实践 目录 Java篇 一、基础算法 七种基础排序 二叉堆 K选取问题 链表判环问题 N皇后问题 两指针扫描算法举例 位运算(求首个bit1,求bit1的个数,寻找奇数项) 最小栈的实现 横纵有...

qcer
2017/12/20
0
0
动态规划经典题目:最大连续子序列和

给定k个整数的序列{N1,N2,...,Nk },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= k。最大连续子序列是所有连续子序中元素和最大的一个,例如给定序列{ -2, 11, -4,...

HeroHY
2017/04/28
170
0
Google 面试题 | 数组的度数

专栏 | 九章算法 网址 | http://www.jiuzhang.com 1.题目描述 给定元素全为非负整数的非空数组nums,数组的度等于出现最多的元素的次数。找到具有和nums相同度的连续子串的最小长度。 样 例 ...

2018/02/24
0
0
剑指offer 30. 连续子数组的最大和

原题 题目: HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解...

dby_freedom
2018/11/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

UAVStack功能上新:新增JVM监控分析工具

UAVStack推出的JVM监控分析工具提供基于页面的展现方式,以图形化的方式展示采集到的监控数据;同时提供JVM基本参数获取、内存dump、线程分析、内存分配采样和热点方法分析等功能。 引言 作为...

宜信技术学院
11分钟前
3
0
MySQL的5种时间类型的比较

日期时间类型 占用空间 日期格式 最小值 最大值 零值表示 DATETIME 8 bytes YYYY-MM-DD HH:MM:SS 1000-01-01 00:00:00 9999-12-31 23:59:59 0000-00-00 00:00:00 TIMESTAMP 4 bytes YYYY-MM......

物种起源-达尔文
18分钟前
4
0
云服务OpenAPI的7大挑战,架构师如何应对?

阿里妹导读:API 是模块或者子系统之间交互的接口定义。好的系统架构离不开好的 API 设计,而一个设计不够完善的 API 则注定会导致系统的后续发展和维护非常困难。比较好的API设计样板可以参...

阿里云官方博客
21分钟前
1
0
Rancher + VMware PKS实现全球数百站点的边缘K8S集群管理

Sovereign Systems是一家成立于2007年的技术咨询公司,帮助客户将传统数据中心技术和应用程序转换为更高效的、基于云的技术平台,以更好地应对业务挑战。曾连续3年提名CRN,并且在2012年到2...

RancherLabs
26分钟前
4
0
6、根据坐标,判断该坐标是否在地图区域范围内

最近在写配送区域相关的代码,具体需求如下: 根据腾讯地图划分配送区域,总站下边设多个配送分站,然后将订单中的收货地址将其分配给不同的配送分站。 1、地图区域划分(腾讯地图) 1.1、H...

有一个小阿飞
28分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部