53. Maximum Subarray

53. Maximum Subarray

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: 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.

class Solution { public int maxSubArray(int[] nums) { int maxSum = Integer.MIN_VALUE; int curSum = 0; int left = 0, right = 0; while (right < nums.length) { curSum += nums[right]; maxSum = Math.max(maxSum, curSum); right++; if (curSum < 0) { curSum = 0; left = right; } } return maxSum; }}

public class Solution { public int maxSubArray(int[] nums) { int currSum = nums[0], maxSum = nums[0]; for(int i = 1; i < nums.length; i++) { currSum = (currSum < 0) ? nums[i] : (currSum + nums[i]); if (currSum > maxSum) { maxSum = currSum; } } return maxSum; }}

class Solution: def maxSubArray(self, nums: List[int]) -> int: res = nums[0] cur = nums[0] for i in range(1, len(nums)): cur += nums[i] if cur < nums[i]: cur = nums[i] res = max(res, cur) return res

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