首页 > 代码库 > 【LeetCode】053. Maximum Subarray
【LeetCode】053. 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
.
题解:
由于是连续子序列这个限制,所以如果k+1这个元素之前的和是小于0的,那么对于增大k+1这个元素从而去组成最大子序列是没有贡献的,所以可以把sum置0处理。
本质上是DP问题。,只是要先求出sum。
Solution 1 ()
class Solution { public: int maxSubArray(vector<int>& nums) { int res = INT_MIN, sum = 0; for (int n : nums) { /* if(sum < 0) sum = 0; sum += A[i]; res = max(res, sum); */ sum = max(sum + n, n); res = max(res, sum); } return cur; } };
Solution 2 (TLE)
class Solution { public: int helper(vector<int> nums, int left, int right) { if(left >= right) return nums[left]; int mid = left + (right - left)/2; int lmax = helper(nums, left, mid-1); int rmax = helper(nums, mid+1, right); int mmax = nums[mid], tmp = mmax; for(int i=mid-1; i>=left; --i) { tmp += nums[i]; mmax = max(tmp, mmax); } tmp = mmax; for(int i=mid+1; i<=right; ++i) { tmp += nums[i]; mmax = max(tmp, mmax); } return max(mmax, max(lmax, rmax)); } int maxSubArray(vector<int>& nums) { if(nums.size() == 0) return 0; return helper(nums,0, nums.size()-1); } };
【LeetCode】053. Maximum Subarray
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。