首页 > 代码库 > LeetCode 53. Maximum Subarray（最大的子数组）

LeetCode 53. Maximum Subarray（最大的子数组）

2024-10-30 12:06:02   207人阅读

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 改变

 

 1 public class Solution 
 2 {
 3     public int maxSubArray(int[] nums) 
 4     {
 5         //    Solution 1:  O(n)
 6         // check param validation.
 7         if(nums == null || nums.length == 0)
 8             return 0;
 9         
10         int sum = 0;
11         int max = Integer.MIN_VALUE;
12  
13         // iterate nums array.
14         for (int i = 0; i < nums.length; i++) 
15         {
16             // choose a larger one between current number or (previous sum + current number).
17             sum = Math.max(nums[i], sum + nums[i]);
18             max = Math.max(max, sum);    // choose the larger max.
19         }
20  
21         return max;
22     }
23     
24     
25     
26 }

 

Java Solution 2: 

Runtime beats 71.37% 

完成日期：03/28/2017

关键词：Array

关键点：Kadane‘s Algorithm

 

 1 public class Solution 
 2 {
 3     public int maxSubArray(int[] nums) 
 4     {
 5         int max_ending_here = 0;
 6         int max_so_far = Integer.MIN_VALUE;
 7         
 8         for(int i = 0; i < nums.length; i++)
 9         {  
10             if(max_ending_here < 0) 
11                  max_ending_here = 0;  
12             max_ending_here += nums[i];  
13             max_so_far = Math.max(max_so_far, max_ending_here);   
14         }  
15         return max_so_far; 
16     }
17     
18     
19     
20 }

 

Java Solution 3: 

Runtime beats 29.96% 

完成日期：03/29/2017

关键词：Array

关键点：Divide and Conquer

 

 1 public class Solution 
 2 {
 3     public int maxSubArray(int[] nums) 
 4     {
 5         // Solution 3: Divide and Conquer. O(nlogn)
 6         if(nums == null || nums.length == 0)
 7             return 0;
 8         
 9         
10         return Max_Subarray_Sum(nums, 0, nums.length-1);
11     }
12     
13     public int Max_Subarray_Sum(int[] nums, int left, int right)
14     {
15         if(left == right)    // base case: meaning there is only one element.
16             return nums[left];
17         
18         int middle = (left + right) / 2;    // calculate the middle one.
19         
20         // recursively call Max_Subarray_Sum to go down to base case.
21         int left_mss = Max_Subarray_Sum(nums, left, middle);    
22         int right_mss = Max_Subarray_Sum(nums, middle+1, right);
23         
24         // set up leftSum, rightSum and sum.
25         int leftSum = Integer.MIN_VALUE;
26         int rightSum = Integer.MIN_VALUE;
27         int sum = 0;
28         
29         // calculate the maximum subarray sum for right half part.
30         for(int i=middle+1; i<= right; i++)
31         {
32             sum += nums[i];
33             rightSum = Integer.max(rightSum, sum);
34         }
35         
36         sum = 0;    // reset the sum to 0.
37         
38         // calculate the maximum subarray sum for left half part.
39         for(int i=middle; i>= left; i--)
40         {
41             sum += nums[i];
42             leftSum = Integer.max(leftSum, sum);
43         }
44         
45         // choose the max between left and right from down level.
46         int res = Integer.max(left_mss, right_mss);
47         // choose the max between res and middle range.
48         
49         return Integer.max(res, leftSum + rightSum);
50         
51     }
52     
53 }

参考资料：

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

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

 

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

 

LeetCode 53. Maximum Subarray（最大的子数组）


联系
我们