【LeetCode】53. Maximum Subarray

问题描述

https://leetcode.com/problems/maximum-subarray/#/description

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

计算数组中的最大子串和。

算法分析

参考自:https://discuss.leetcode.com/topic/7447/o-n-java-solution

因为数组中有正数也有负数,每加一个正数,子串值增加,每加一个负数,子串值减少,所以,应该尽量跳过负数。

下面使用sum表示从左往右遍历数组时的当前较大子串和,总之,当前的那个数必须计算在sum中。sum初始化为nums[0],接下来遍历到位置1,有如下情况:

  1. 如果nums[0]>=0,则sum = sum + nums[1]
  2. 如果nums[0]<0,则sum = nums[1]

同理,有一般式:sum = nums[i] + (sum<0?0:sum)
使用max记录sum变化过程中的最大值,即为答案。

代码

        public int maxSubArray(int[] nums) {
	    	int max = Integer.MIN_VALUE, sum = 0;
	        for (int i = 0; i < nums.length; i++) {
	        	sum = nums[i] + (sum < 0 ? 0:sum);
	            max = sum > max ? sum:max;
	        }
	        return max;
	    }

我的微信公众号
![](http://upload-images.jianshu.io/upload_images/3093748-7c07998b7495defc.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)