LeetCode 53. Maximum Subarray(最大的子数组)

时间:2024-08-23 14:34:44

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.


题目标签:Array
  这道题目给了我们一个array, 让我们找到一个连续的子数组,它的sum是最大的。题目说明有O(n) 方法和 Divide and conquer 方法。
  我们先来看一下O(n) 方法:
    遍历array,对于每一个数字,我们判断,(之前的sum + 这个数字) 和 (这个数字) 比大小,如果(这个数字)自己就比 (之前的sum + 这个数字) 大的话,那么说明不需要再继续加了,直接从这个数字,开始继续,因为它自己已经比之前的sum都大了。
    反过来,如果 (之前的sum + 这个数字)大于 (这个数字)就继续加下去。
    这个方法和Kadane Algorithm 差不多, Kadane 的算法是,如果之前的sum 小于0了,就重新计算sum,如果sum不小于0,那么继续加。
  接着看一下Divide and conquer 方法:
    对于任何一个array来说,有三种可能:
      1。它的maximum subarray 落在它的左边;
      2。maximum subarray 落在它的右边;
      3。maximum subarray 落在它的中间。
    对于第一,二种情况,利用二分法就很容易得到,base case 是如果只有一个数字了,那么就返回。
    对于第三种情况,如果落在中间,那么我们要从左右两边返回的两个 mss 中,挑出一个大的,再从 (左右中大的值) 和 (左+右)中挑出一个大的。具体看下面代码。
  

Java Solution 1:

Runtime beats 71.37%

完成日期:03/28/2017

关键词:Array

关键点:基于 Kadane's Algorithm 改变

 public class Solution
{
public int maxSubArray(int[] nums)
{
// Solution 1: O(n)
// check param validation.
if(nums == null || nums.length == 0)
return 0; int sum = 0;
int max = Integer.MIN_VALUE; // iterate nums array.
for (int i = 0; i < nums.length; i++)
{
// choose a larger one between current number or (previous sum + current number).
sum = Math.max(nums[i], sum + nums[i]);
max = Math.max(max, sum); // choose the larger max.
} return max;
} }

Java Solution 2:

Runtime beats 71.37%

完成日期:03/28/2017

关键词:Array

关键点:Kadane's Algorithm

 public class Solution
{
public int maxSubArray(int[] nums)
{
int max_ending_here = 0;
int max_so_far = Integer.MIN_VALUE; for(int i = 0; i < nums.length; i++)
{
if(max_ending_here < 0)
max_ending_here = 0;
max_ending_here += nums[i];
max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;
} }

Java Solution 3:

Runtime beats 29.96%

完成日期:03/29/2017

关键词:Array

关键点:Divide and Conquer

 public class Solution
{
public int maxSubArray(int[] nums)
{
// Solution 3: Divide and Conquer. O(nlogn)
if(nums == null || nums.length == 0)
return 0; return Max_Subarray_Sum(nums, 0, nums.length-1);
} public int Max_Subarray_Sum(int[] nums, int left, int right)
{
if(left == right) // base case: meaning there is only one element.
return nums[left]; int middle = (left + right) / 2; // calculate the middle one. // recursively call Max_Subarray_Sum to go down to base case.
int left_mss = Max_Subarray_Sum(nums, left, middle);
int right_mss = Max_Subarray_Sum(nums, middle+1, right); // set up leftSum, rightSum and sum.
int leftSum = Integer.MIN_VALUE;
int rightSum = Integer.MIN_VALUE;
int sum = 0; // calculate the maximum subarray sum for right half part.
for(int i=middle+1; i<= right; i++)
{
sum += nums[i];
rightSum = Integer.max(rightSum, sum);
} sum = 0; // reset the sum to 0. // calculate the maximum subarray sum for left half part.
for(int i=middle; i>= left; i--)
{
sum += nums[i];
leftSum = Integer.max(leftSum, sum);
} // choose the max between left and right from down level.
int res = Integer.max(left_mss, right_mss);
// choose the max between res and middle range. return Integer.max(res, leftSum + rightSum); } }

参考资料:

http://www.cnblogs.com/springfor/p/3877058.html

https://www.youtube.com/watch?v=ohHWQf1HDfU

LeetCode 算法题目列表 - LeetCode Algorithms Questions List