剑指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 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 乱序字符串题目分析代码

给出一个字符串数组S,找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串,那么他存在一个字母集合相同,但顺序不同的字符串也在S中。

843
来自专栏赵俊的Java专栏

合并排序数组 Ⅱ

1214
来自专栏从流域到海域

JavaScript闭包详解

JavaScript闭包详解 闭包就是由函数创造的一个词法作用域,里面创建的变量被引用后,可以在这个词法环境之外自由使用(维基百科)。 闭包,官方对闭包...

1938
来自专栏Crossin的编程教室

【Python 第52课】 元组

上一次pygame的课中有这样一行代码: x, y = pygame.mouse.get_pos() 这个函数返回的其实是一个“元组”,今天我们来讲讲这个东西。...

3197
来自专栏Python小屋

Python中lambda表达式的常见用法

非常抱歉,昨天发的代码中有一处小错误,已通过留言的方式进行了纠正,详情请见【详解Python列表推导式】 lambda表达式常用来声明匿名函数,即没有函数名字的...

2829
来自专栏互联网杂技

js中type of与instance的区别

JavaScript 中 typeof 和 instanceof 常用来判断一个变量是否为空,或者是什么类型的。但它们之间还是有区别的: typeof type...

3175
来自专栏编程

浅谈Go语言中闭包的使用

闭包(Closure),又称词法闭包(Lexical Closure)或函数闭包(function closures),是引用了自由变量的函数。这个被引用的自由...

2378
来自专栏desperate633

浅谈javascript中的的闭包作用域链引出闭包利用闭包突破作用域链的三种方法小结

闭包可以说是javascript中最令人迷惑的概念了。需要我们在实践中去慢慢理解,在实际编码中,由于闭包的效率和会产生大量无法销毁的内存,所以原则是尽量少使用闭...

561
来自专栏Python中文社区

Python函数的基本特征详解

今天开始,我们来讲讲函数,简而言之一个函数就是将一些语句集合在一起的部件,它们能够不止一次的在程序中运行。函数还能计算出一个返回值,并能够改变作为函数输入的参数...

894
来自专栏司想君

JavaScript闭包,只学这篇就会了

昨天发的文章,排版出现了重大失误。让大家的眼睛受累了。今天再发一遍。 这篇文章使用一些简单的代码例子来解释JavaScript闭包的概念,即使新手也可以轻松参透...

2628

扫描关注云+社区