Description
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example
1 | Input: [-2,1,-3,4,-1,2,1,-5,4], |
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.
Solution
DP Solution1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i < nums.length; i++){
dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
max = Math.max(dp[i], max);
}
return max;
}
}
Divide and Conquer Solution1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39public class Solution {//divdie and conquer
public int maxSubArray(int[] nums) {
return Subarray(nums, 0 ,nums.length -1 );
}
public int Subarray(int[] A,int left, int right){
if(left == right) return A[left];
int mid = left + (right - left) / 2;
int leftSum = Subarray(A,left,mid);// left part
int rightSum = Subarray(A,mid+1,right);//right part
int crossSum = crossSubarray(A,left,right);// cross part
if(leftSum >= rightSum && leftSum >= crossSum){// left part is max
return leftSum;
}
if(rightSum >= leftSum && rightSum >= crossSum){// right part is max
return rightSum;
}
return crossSum; // cross part is max
}
public int crossSubarray(int[] A,int left,int right){
int leftSum = Integer.MIN_VALUE;
int rightSum = Integer.MIN_VALUE;
int sum = 0;
int mid = left + (right - left) / 2;
for(int i = mid; i >= left ; i--){
sum = sum + A[i];
if(leftSum < sum){
leftSum = sum;
}
}
sum = 0;
for(int j = mid + 1; j <= right; j++){
sum = sum + A[j];
if(rightSum < sum){
rightSum = sum;
}
}
return leftSum + rightSum;
}
}