文档章节

最大连续子序列和

z
 zhouplus
发布于 2016/04/13 03:20
字数 1382
阅读 25
收藏 1

Question:

输入一组整数,求出这组数字子序列和中最大值。也就是只要求出最大子序列的和,不必求出最大的那个序列。例如:

序列:-2 ,11, -4, 13, -5, -2,则最大子序列和为20。

序列:-6 ,2, 4, -7, 5, 3, 2 ,-1 ,6, -9 ,10 ,-2,则最大子序列和为16。

算法1:穷举法

/**
	 * 穷举法
	 * 时间复杂度0(n^3)
	 * @param arr
	 * @return
	 */
	public static int maxSubseqSum1(int[] arr){
		int thisSum,maxSum = 0;
		int i,j,k;
		for (i = 0; i < arr.length; i++) {//i是子列左端位置
			for (j = i; j < arr.length; j++) {//j是子列右端位置
				thisSum = 0;//thisSum是从arr[i]到a[j]的子列和
				for (k = i; k < j; k++) {
					thisSum += arr[k];
				}
				if (thisSum > maxSum) {//如果刚得到这个子列和更大
					maxSum = thisSum;//则更新结果
				}//j循环结束
			}//i循环结束
		}		
		return maxSum;
	}

算法2:改进的穷举法,去掉一层for循环,去掉重复操作

/**
	 * 穷举法之二。也是一种穷举法,相比较第一种穷举法撤出了一层for循环,更加直观。而且没有多余重复的操作
	 * 时间复杂度0(n^2)
	 * @param arr
	 * @return
	 */
	public static int maxSubseqSum2(int[] arr){
		int thisSum,maxSum = 0;
		int i,j;
		for (i = 0; i < arr.length; i++) {//i是子列左端位置
			thisSum = 0; //thisSum是从arr[i]到arr[j]的子列和
			for (j = i; j < arr.length; j++) {//j是子列右端位置
				thisSum += arr[j];
				/*对于相通的i,不同的j,只要在j-1次循环的基础上累加1项即可*/
				if (thisSum > maxSum) {//如果刚得到这个子列和更大
					maxSum = thisSum;//则更新结果
				}
			}//j循环结束
		}//i循环结束		
		return maxSum;
	}

算法3:递归法(分治法)

声明:这里借鉴别人的博文:分治法借鉴博客

/**
	 * 分而治之
	 * 时间复杂度0(nlogn)
	 * @param arr
	 * @return
	 */
	public static int maxSubseqSum3(int[] arr,int left,int right){
		if (left == right) {
			if (arr[left] > 0) {
				return arr[left];
			}else{
				return 0;
			}	
		}
		
		int center = (left+right)/2;
		int maxleftSum = maxSubseqSum3(arr, left, center);
		int maxRightSum = maxSubseqSum3(arr, center+1, right);
		
		//求出以左边对后一个数字结尾序列的最大值
		int maxleftBorderSum = 0,leftBorderSum = 0;
		for (int i = center; i >= left; i--) {
			leftBorderSum += arr[i];
			if (leftBorderSum > maxleftBorderSum) {
				maxleftBorderSum = leftBorderSum;
			}
		}
		
		//求以右边对后一个数字结尾的序列最大值
		int maxRightBorderSum = 0,rightBorderSum = 0;
		for (int j = center+1; j <= right; j++) {
			rightBorderSum += arr[j];
			if (rightBorderSum > maxRightBorderSum) {
				maxRightBorderSum = rightBorderSum;
			}
		}
		
		//返回左边最大,右边最大,和跨域最大的一个数字
		int sum = maxleftBorderSum+ maxRightBorderSum;
		
		if(maxleftSum >= maxRightSum && maxleftSum >= sum)
			return maxleftSum;
		else if(maxRightSum >= maxleftSum && maxRightSum >= sum)
			return maxRightSum;
		else
			return sum;
	}

算法4:在线处理(动态规划)

将子序列与其子子序列进行问题分割, 得到状态转移方程:MaxSum[i] = max{MaxSum[i-1]+A[i],MaxSum[i-1]+A[i]}

其中MaxSum[i]表示数组前i-1个元素的和

/**
	 * 在线处理
	 * 时间复杂度0(n)  线性算法
	 * @param arr
	 * @return
	 */
	public static int maxSubseqSum4(int[] arr){
		int thisSum = 0,maxSum = 0;
		int i,j;
		for (i = 0; i < arr.length; i++) {//i是子列左端位置
			thisSum += arr[i]; //向右累加
			if(thisSum > maxSum)
				maxSum = thisSum;//发现更大和则更新当前结果
			else if(thisSum < 0)//如果当前子列和为负数
				thisSum = 0;//则不可能使后面的部分和增大,抛弃之
		}//i循环结束		
		return maxSum;
	}

简单测试用例:由于时间较短,所以采用循环运行N次的办法累加时间

public static void main(String[] args) {
		int[] arr1 = new int[] { -2, 11, -4, 13, -5, -2 };
		int[] arr2 = new int[] { -6, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4,
				-7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10,
				-2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1,
				6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5,
				3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2,
				4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9,
				10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2,
				-1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7,
				5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2,
				2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6,
				-9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2 };

		int N = 1000;// 测试算法执行次数
		System.out.println("maxSubseqSum1:" + maxSubseqSum1(arr2));
		System.out.println("maxSubseqSum2:" + maxSubseqSum2(arr2));
		System.out.println("maxSubseqSum3:" + maxSubseqSum3(arr2, 0, arr2.length - 1));
		System.out.println("maxSubseqSum4:" + maxSubseqSum4(arr2));

		long timeStart1 = System.currentTimeMillis();
		for (int i = 0; i < N; i++) {
			maxSubseqSum1(arr2);
		}
		long timeEnd1 = System.currentTimeMillis();
		System.out.println("算法1执行" + N + "次的时间,单位毫秒:" + (timeEnd1 - timeStart1));

		long timeStart2 = System.currentTimeMillis();
		for (int i = 0; i < N; i++) {
			maxSubseqSum2(arr2);
		}
		long timeEnd2 = System.currentTimeMillis();
		System.out.println("算法2执行" + N + "次的时间,单位毫秒:" + (timeEnd2 - timeStart2));

		long timeStart3 = System.currentTimeMillis();
		for (int i = 0; i < N; i++) {
			maxSubseqSum3(arr2, 0, arr2.length - 1);
		}
		long timeEnd3 = System.currentTimeMillis();
		System.out.println("算法3执行" + N + "次的时间,单位毫秒:" + (timeEnd3 - timeStart3));

		long timeStart4 = System.currentTimeMillis();
		for (int i = 0; i < N; i++) {
			maxSubseqSum3(arr2, 0, arr2.length - 1);
		}
		long timeEnd4 = System.currentTimeMillis();
		System.out.println("算法4执行" + N + "次的时间,单位毫秒:" + (timeEnd4 - timeStart4));
	}

测试环境:

java version "1.8.0_66"

Java(TM) SE Runtime Environment (build 1.8.0_66-b17)

Java HotSpot(TM) 64-Bit Server VM (build 25.66-b17, mixed mode)

OS:windows10

Eclipse:4.5.2

测试结果:

© 著作权归作者所有

z
粉丝 2
博文 19
码字总数 8860
作品 0
朝阳
程序员
私信 提问
夕拾算法进阶篇:13)最大连续子序列(动态规划DP)

题目描述 给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个,例如给定序...

jiangpeng59
2017/02/05
0
0
动态规划经典题目:最大连续子序列和

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

HeroHY
2017/04/28
145
0
[LeetCode] 最大连续子序列和或者乘积,以及最长连续子串

题目 Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4],the contiguous subarray......

Finley.Hamilton
2014/11/08
718
2
算法知识梳理(5) - 数组第二部分

一、概要 本文介绍了有关数组的算法第一部分的代码实现,所有代码均可通过 在线编译器 直接运行,算法目录: 找到最小的个数 连续子数组的最大和 连续子数组的最大和(二维) 求数组当中的逆...

泽毛
2017/12/11
0
0
数据结构学习笔记——最大子列和问题

PTA 中国大学MOOC-陈越、何钦铭-数据结构 01-复杂度1 最大子列和问题(20 分) 给定K个整数组成的序列{ N1 , N2 , ..., Nk},“连续子列”被定义为{ Ni , Ni+1 , ..., Nj},其中 1≤i≤j≤K...

fesoncn
2017/10/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分布式协调服务zookeeper

ps.本文为《从Paxos到Zookeeper 分布式一致性原理与实践》笔记之一 ZooKeeper ZooKeeper曾是Apache Hadoop的一个子项目,是一个典型的分布式数据一致性的解决方案,分布式应用程序可以基于它...

ls_cherish
今天
4
0
redis 学习2

网站 启动 服务端 启动redis 服务端 在redis 安装目录下 src 里面 ./redis-server & 可以指定 配置文件或者端口 客户端 在 redis 的安装目录里面的 src 里面 ./redis-cli 可以指定 指定 连接...

之渊
昨天
2
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
昨天
4
0
hash slot(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
昨天
4
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
昨天
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部