LeetCode-53. Maximum Subarray

LeetCode-53. Maximum Subarray

​​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: 6Explanation: [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.

题解：dp[i]存储前面0-i的连续正子串，ans存储dp[0]到dp[i]的最大连续子串，每次加入nums[i]（无论正负）都更新当前ans。当前面0-i的连续子串和小于0时，直接让dp[i]=nums[i]，否则一直让dp[i-1]加上nums[i]。

class Solution {public: int maxSubArray(vector& nums) { vector dp(nums.size(), 0); int ans = nums[0]; dp[0] = nums[0]; for (int i = 1; i < nums.size(); i++){ if (dp[i - 1] >= 0){ dp[i] = dp[i - 1] + nums[i]; ans = max(ans, dp[i]); } else{ dp[i] = nums[i]; ans = max(ans, dp[i]); } } return ans; }};

只用一个变量

class Solution {public: int maxSubArray(vector& nums) { int sum = 0, ans = INT_MIN; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; ans = max(ans, sum); if (sum < 0) { sum = 0; } } return ans; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。