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.
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
题目标签:Array
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