题目要求
1
2
3
4
| 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.
|
即：寻找数列中的一个子数列，该数列中的值得和是所有子数列中最大的。
思路一：divide&conquer
我们可以从数列的中间节点将数列分为两个子数列，则最大的子数列要么在左子列，要么在右子列，要么跨越了左子列和右子列。我们可以分别得出这三种情况下的最大子数列和，并比较得出最大的那个。
divide&conquer即递归思路，将复杂问题分解为简单的小问题分别解决。递归的重点在于覆盖所有可能情况，并且覆盖到基类。
1
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
39
40
41
| public int maxSubArray(int[] nums) {
int start = 0;
int end = nums.length - 1;
return maxSubArray(nums, start, end);
}
public int maxSubArray(int[] nums, int start, int end){
if(start==end){
return nums[start];
}
int mid = (start + end) / 2;
int leftMax = maxSubArray(nums, start, mid);
int rightMax = maxSubArray(nums, mid+1, end);
int leftSumMax = Integer.MIN_VALUE;
int temp = 0;
do{
temp += nums[mid];
if(temp>leftSumMax){
leftSumMax = temp;
}
}while((--mid)>=start);
temp = 0;
mid = (start + end)/2 + 1;
int rightSumMax = Integer.MIN_VALUE;
do{
temp += nums[mid];
if(temp>rightSumMax){
rightSumMax = temp;
}
}while((++mid)<=end);
int midMax = leftSumMax + rightSumMax;
return Math.max(Math.max(leftMax, rightMax), midMax);
}
|
思路二：divide&conquer2 recursion##
上面是将数组从中划分为两个子数组,这里我们还可以划分为nums[n-1]和nums[n]。这样我们就可以将右子列的情况简化为直接返回右子列的值。我们只需要考虑左子列的最大和以及跨越了左右的中子列的最大值。所以我们需要记录两个值，第一个是当前最大和，还有一个是到nums[n-1]的最大子列和。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
|