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

相关文章

来自专栏分布式系统和大数据处理

正则表达式教程

1045
来自专栏Python小屋

Python版堆排序算法

其他排序算法的Python实现请参考:Python版归并排序算法(附Python程序__name__属性用法演示视频),侏儒排序算法原理与Python实现,Py...

2985
来自专栏desperate633

LintCode 交叉字符串题目分析代码

样例 比如 s1 = "aabcc" s2 = "dbbca" 当 s3 = "aadbbcbcac",返回 true. 当 s3 = "aadbbba...

1474
来自专栏轮子工厂

一口气吃下数组的存储方式

Long long ago,我们讲到了数组《聊一聊数组背后的那点事》,这个已经是迈进指针的第一步了,主要的内容是一维数组,今天我们将讲述二维数组。当结束了今天的...

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

P3809 【模版】后缀排序

题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

2608
来自专栏python3

python random模块

随机输出一个0~4的数字和range()输出的数字,去比较。猜对了,就是字母,否则是数字

722
来自专栏好好学java的技术栈

“365算法每日学计划”:05打卡-图解冒泡排序(多解法)

1073
来自专栏漫漫深度学习路

pytorch学习笔记(十七):python 端扩展 pytorch

pytorch 虽然提供了很多的 op 使得我们很容易的使用。但是当已有的 op 无法满足我们的要求的时候,那就需要自己动手来扩展。 pytorch 提供了两种...

2807
来自专栏小樱的经验随笔

UVA 11636-Hello World!(水题,猜结论) UVA11636-Hello World!

UVA11636-Hello World! Time limit: 1.000 seconds When you first made the computer ...

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

488. 快乐数

一个数是不是快乐是这么定义的:对于一个正整数,每一次将该数替换为他每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,或是无限循环但始终变不到1。如果可...

1433

扫码关注云+社区