（Java）leetcode-53 Maximum Subarray （动态规划）

蔚落 2022-03-07 07:20 241阅读 0赞

# 题目 #

【最大子序和】

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
    Output: 6

Explanation: \[4,-1,2,1\] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

# 思路（动态规划） #

遍历数组的过程中求累加和，当某个元素比累加和还大（也就是说，前面的累加和为负数），那么重置累加和（舍弃前面所求的和），改为从该元素开始求和，因为最大子序只可能从当前元素开始产生。  
设置一个int用来保存整个遍历过程中产生的**最大的累加和**，每次循环的最后检查累加和是否达到了新高，若是，则更新最大和。  
这实际上是一种简化的动态规划解法，因为只用一个int来跟踪最大和。

> 这个问题由Jon Bentley讨论（1984年9月第27卷第9期ACM P885通讯）
> 
> 以下段落是从他的论文中复制的（稍作修改）
> 
> 对数组进行操作的算法：它从左端开始（元素A \[1\]）并扫描到右端（元素A \[n\]），跟踪到目前为止看到的最大和子向量。 最大值最初为A\[0\]。 假设我们已经解决了A \[1 … i - 1\]的问题; 我们怎么能把它扩展到A \[1 … i\]？ 最大值第一个I元素中的和是第一个i - 1元素（我们称之为MaxSoFar）的最大和，或者是在位置i（我们称之为MaxEndingHere）结束的子向量的和。
> 
> MaxEndingHere是A \[i\]加上之前的MaxEndingHere，或者只是A \[i\]，以较大者为准。

时间复杂度O(n)。

# 代码 #

class Solution { 
        public int maxSubArray(int[] nums) { 
        	int maxSum = Integer.MIN_VALUE;//最大和
        	int sum = 0;//累加和
    	    for(int i = 0; i<nums.length; i++){ 
    	    	sum += nums[i];//累加操作
    
    	    	if(nums[i] > sum)//若当前元素比累加和还大，说明前面的和为负数，可以舍弃，因为最大子序只可能从当前元素开始产生
    	    		sum = nums[i];
    
    	    	if(sum > maxSum)//更新最大和
    	    		maxSum = sum ;
        	}
        	return maxSum;
    
        }
           
    }

## 提交结果 ##

Runtime: 5 ms, faster than 100.00% of Java online submissions for Maximum Subarray.  
Memory Usage: 39.9 MB, less than 9.09% of Java online submissions for Maximum Subarray.