本文主要是介绍Leetcode83: Maximum Subarray,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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
.
现在对线性时间解法做一下解释,属于一种DP问题。已知了前k个元素的最大子序列和为maxSub(已经被记录下来了),以及一个临时和sum,如果添加了第k+1这个元素,由于是连续子序列这个限制,所以如果k+1这个元素之前的和是小于0的,那么对于增大k+1这个元素从而去组成最大子序列是没有贡献的,所以可以把sum 置0。举个例子,-1, -2 ,4, -5, 7这里假定7为第k+1个元素,那么很明显可以看出,之前的sum = -5 + 4 =-1,那么这样对于7来说只会减少它,所以直接置sum = 0, 0 + 7才能得到正确的答案。再拓展这个数组, -1, -2, 4, -5, 7, 1 这里1之前的sum = 7 > 0,对于后面的1来组成最大子序列是有贡献的,所以sum = 7 + 1 =8。再注意一点,只要sum不减到负数,中间出现小于0的元素是没关系的,sum仍然可以继续累加。
class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();if(n==0)return 0;int maxsum = nums[0];int sum = nums[0];for(int i = 1; i < n; i++){if(sum < 0)sum = 0;sum += nums[i];maxsum = max(sum, maxsum); }return maxsum;}
};
这篇关于Leetcode83: Maximum Subarray的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!