剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n)

分析:统计连续子数组的最大值最直观的方法就是遍历数组n次,每次以a[i]作为子数组的起点,然后将a[i]后面的数字依次纳入数组中,计算最大值。这种方式的时间复杂度为O(n^2),显然不符合要求。下面我们根据数组自身的特点来统计连续子数组的最大值。

我们尝试从左向右遍历数组,并且进行累加。我们就会发现:如果当数组累加到a[i]后,累加的结果反而小于a[i]本身,那就说明a[0]+……+a[i-1]是一个负数。那么这个负数会拖累a[i]后面累加的结果,即:a[0]+……+a[i-1]+a[i]+……+a[n] < a[i]+……+a[n]。既然如此,当我们发现累加进行到a[i]时,如果累加的结果反而小于a[i]本身,就把a[i]前面的所有数全都丢掉,累加从a[i]重新开始。与此同时,用一个全局变量记录当前子数组的最大值。那么当扫描完一遍数组后,那个最大值就是我们要的结果。代码如下:

/**
 * 题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)
 * @author 大闲人柴毛毛
 * @date 2016年3月16日
 */
public class MaxSubArray {
	
	/**
	 * 计算子数组和的最大值
	 * @param a 数组
	 * @return 返回子数组和的最大值
	 */
	private static boolean result = true;//用于标识本函数运行过程是否正常
	public static int getMaxSubArray(int[] a){
		//数组为空
		if(a==null || a.length<=0){
			System.out.println("数组为空!");
			result = false;
			return -1;
		}
		
		int max = 0;//记录当前子数组最大值
		int sum = 0;//记录当前子数组的和
		//扫描数组
		for(int i=0;i<a.length;i++){
			//计算当前子数组的和
			sum += a[i];
			
			//若a[i]比sum大
			if(a[i]>sum){
				//丢掉a[i]之前累加结果,把a[i]作为子数组的起点
				sum = a[i];
				max = a[i];
			}
			
			//若a[i]比sum小,则判断sum是否>max,若sum>max,则更新max
			if(sum > max)
				max = sum;
		}
		
		return max;
	}
	
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		int[] a = {1,-2,3,10,-4,7,2,1,-5};
		System.out.println("函数执行结果:"+result);
		System.out.println("最大值="+getMaxSubArray(a));
	}
	
}

运行结果:

函数执行结果:true

最大值=19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏青枫的专栏

【java面试题001】Boolean b = new Boolean(“abcde”); 会编译报错吗?

  不会编译报错,在Boolean的构造函数中,除了”true”和”false”之外的字符串虽然不会造成编译错误,但是会返回false。

691
来自专栏Python小屋

Python内置函数max()高级用法

不管是排序还是选取最大值或者最小值,都应该有个规则或者顺序,而平时我们所说的最大值或最小值实际上也是在某种排序规则或顺序下的最大值和最小值。Python内置函数...

2504
来自专栏和蔼的张星的图像处理专栏

46. 主元素解1解2

给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一。假定一定存在这样的主元素。 样例 给出数组[1,1,1,1,2,2,2],...

632
来自专栏玄魂工作室

输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字

要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和...

741
来自专栏运维技术迷

连仕彤博客[Python笔记] 判断0-9数字在字符串中出现的次数

要求 给定一些数字(0-9范围之间),判断数字在字符串中出现的次数。 例子的排序是依照算法的效率(时间复杂度)从低到高 例子1   # 定义数字 num = ...

3937
来自专栏Hongten

python开发_函数的参数传递

在这个用例中,我们要讨论的是关于函数的传参问题 我所使用的python版本为3.3.2

744
来自专栏开发与安全

excel中的 sumif 和 countif 函数分析详解

如上图所示: E3=COUNTIF(C2:C10,">"&E2)-COUNTIF(C2:C10,">="&F2) 即用大于50的个数减去大于等于100的个数就...

1815
来自专栏数据结构与算法

08:字符替换

08:字符替换 总时间限制: 1000ms 内存限制: 65536kB描述 把一个字符串中特定的字符全部用给定的字符替换,得到一个新的字符串。 输入只有一...

3555
来自专栏Golang语言社区

【Go 语言社区】Go语言类型转换

类型转换是一种可变从一种数据类型转换成另一种数据类型。例如,如果要存储一个long值转成一个简单的整数,那么可以强制类型转换long为int。可以从一种类型使用...

33614
来自专栏Coding迪斯尼

面试算法,在绝对值排序数组中快速查找满足条件的元素配对

1061

扫码关注云+社区