首页 > 代码库 > 53. Maximum Subarray
53. Maximum Subarray
https://leetcode.com/problems/maximum-subarray/description/
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.
click to show more practice.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Sol 1:
public class Solution { public int maxSubArray(int[] nums) { // DP // Time O（N） Space O(1) int maxLocal = nums[0]; int global = nums[0]; for (int i = 1; i < nums.length; ++i){ maxLocal = Math.max(nums[i], nums[i] + maxLocal); global = Math.max(global, maxLocal); } return global; } }
Sol 2:
(Unsolved -- don‘t know what cur_min is doing here...)
public class Solution { public int maxSubArray(int[] nums) { // Time O（n） Space O(n) return mcss(nums, 0, nums.length); } // find the max sum of the continuous array public static int mcss(int[] nums, int begin, int end){ final int n = end - begin; int[] sum = new int[n + 1]; // the sum of n elements in the front int result = Integer.MIN_VALUE; int cur_min = sum[0]; for (int i = 1; i <= n; i++){ sum[i] = sum[i - 1] + nums[begin + i - 1]; } for (int i = 1; i <= n; i++){ result = Math.max(result, sum[i] - cur_min); cur_min = Math.min(cur_min, sum[i]); } return result; } }
53. Maximum Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。