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: 6
Explanation: [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) {
}
}
Problem Clarification
We need to consider sum of contiguous elements.Idea - 1
Try each of
subarray and keep track of the max sum. Time , space 
.
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int maxsum = Integer.MIN_VALUE;
for(int i = 0; i < n; ++i)
{
int sum = 0;
for(int j = i; j < n; ++j)
{
sum += nums[j];
maxsum = Math.max(maxsum, sum);
}
}
return maxsum;
}
}
Runtime: 105 ms, faster than 5.03% of Java online submissions for Maximum Subarray.
Memory Usage: 49.3 MB, less than 5.05% of Java online submissions for Maximum Subarray.Idea - 2
While considering if we should include
to the running sum, if the sum of 
does not help then we start a fresh run starting at . The algorithm has time 
and space .
class Solution {
public int maxSubArray(int[] nums) {
int maxsum = Integer.MIN_VALUE;
int sum = 0;
for(int i = 0; i < nums.length; ++i)
{
sum = Math.max(sum+nums[i], nums[i]);
maxsum = Math.max(maxsum, sum);
}
return maxsum;
}
}
Runtime: 1 ms, faster than 97.15% of Java online submissions for Maximum Subarray.
Memory Usage: 38.4 MB, less than 92.18% of Java online submissions for Maximum Subarray.Idea - 3
If we break the array in middle and find solutions: one to the left and other to the right, then the global solution would be the maximum among these two solutions and the solution that cross boundary. Time
and stack space 
.
class Solution {
public int maxSubArray(int[] nums) {
return maxSum(nums, 0, nums.length-1);
}
private int maxSum(int[] A, int lo, int hi)
{
if(lo > hi)
{
return 0;
}
if(lo == hi)
{
return A[lo];
}
int mid = lo+(hi-lo)/2;
int leftSum = maxSum(A, lo, mid);
int rightSum = maxSum(A, mid+1, hi);
// last element to the left and first element
// to the right must be in the crossing solution
//
int middleSum = mid+1 > hi ? 0 : A[mid+1];
middleSum += A[mid];
// can we increase going to the right
//
int sum = middleSum;
for(int j = mid+2; j <= hi; ++j)
{
sum += A[j];
middleSum = Math.max(middleSum, sum);
}
// can we increase going to the left
//
sum = middleSum;
for(int j = mid-1; j >= lo; --j)
{
sum += A[j];
middleSum = Math.max(middleSum, sum);
}
return Math.max( middleSum, Math.max(leftSum, rightSum) );
}
}
Runtime: 3 ms, faster than 74.42% of Java online submissions for Maximum Subarray.
Memory Usage: 38.5 MB, less than 92.00% of Java online submissions for Maximum Subarray.
.
and space 
and space 
. If 
then we have 
. Thus if two triplets has the same any two elements then the triplets are not unique. We need to ensure that two triplets either have different a’s or different b’s. If we ensure the following two conditions, we would collect all unique solutions:
1. We batch all triplets that have a as the first element but have different b’s. All elements in such a batch thus differ in b and would be considered as unique solutions.
2. After step 1, we now move onto a different a (never considering the a in an earlier batch) and repeat step 1.
We would not miss a solution, because for each solution triplet, the first of its three elements (in sorted order) must be in one of the batches – since we consider each distinct element as the first element in some batch. For that batch, we have considered all distinct elements that come after a (in sorted order) as the second element. Given two elements the third element is uniquely determined.
The algorithm has 
time complexity and 
and space 
.
programmingpuzzles 