想了一个非常复杂的解法，大概方法是先向右查找，如果添加右边一个情况会更好就则继续向右，如果删去左边一个情况会更好，就删去左边一个，但有时候局部情况不等于整体情况，所以会出问题，有的 case 过不了，就非常 sad。
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
42
43
44
| class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==1){
return nums[0];
}
int left=0;
int right=0;
int maxSum=nums[0];
int nowSum=nums[0];
while(right<nums.length-1 && left<=right){
if(nums[right+1]>=0){
nowSum+=nums[right+1];
maxSum=nowSum>maxSum?nowSum:maxSum;
right++;
}else{
if(nums[left]>0 || -nums[left]<=nums[right+1] || left==right){
nowSum+=nums[right+1];
maxSum=nowSum>maxSum?nowSum:maxSum;
right++;
}else{
nowSum-=nums[left];
maxSum=nowSum>maxSum?nowSum:maxSum;
left++;
}
}
System.out.println(left);
System.out.println(right);
System.out.println(nowSum);
System.out.println(maxSum);
System.out.println("++++++++");
}
while(left<nums.length-1){
nowSum-=nums[left];
maxSum=nowSum>maxSum?nowSum:maxSum;
left++;
System.out.println(left);
System.out.println(right);
System.out.println(nowSum);
System.out.println(maxSum);
System.out.println("++++++++");
}
return maxSum;
}
}
|
看了答案，才理解该怎么解。先寻找局部最大，意思就是如果当前数字加上之前的最大还比现在的数字小，说明可以放弃之前的最大，将当前数字作为最优大了。然后将比较大的局部最大赋值给全局最大。
这个思路的确很有意思，即解决了我之前寻找全局最大可能找不到的问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==1)
return nums[0];
int allMax=nums[0];
int localMax=nums[0];
for(int i=1;i<nums.length;i++){
int add=localMax+nums[i];
localMax=add>nums[i]?add:nums[i];
allMax=allMax>localMax?allMax:localMax;
}
return allMax;
}
}
|
只击败了 20.9% 的人，看起来的确效率不高。
搜索了以后发现，这个问题没这么简单，它的最佳线性解法是 Kadane 算法，由 CMU 的 Kadane 教授在 1984 年提出。
算法描述：
- 遍历该数组， 在遍历过程中， 将遍历到的元素依次累加起来， 当累加结果小于或等于 0 时， 从下一个元素开始，重新开始累加。
- 累加过程中， 要用一个变量(max_so_far)记录所获得过的最大值
- 一次遍历之后， 变量 max_so_far 中存储的即为最大子片段的和值。
使用 Wikipedia 中的 Python 代码的含义，书写 Java 代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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;
}
}
|
用时和前面的代码接近。
以下对代码的理解摘自https://blog.csdn.net/lengxiao1993/article/details/52303492
- 最大子片段是可以为空的， 空片段的和值是 0。 这一点必须要明确， 不然会无法理解算法的正确性， 所以当给定的数列中，求和为负数的时候，例如【-2，1， -3】， 算法会返回最大求和值 0， 因为默认该数组的最大子片段是一个空序列。
- 最大子片段中不可能包含求和值为负的前缀。 例如 【-2， 1，4】 必然不能是最大子数列， 因为去掉值为负的前缀后【-2，1】， 可以得到一个更大的子数列 【4】、
- 所以在遍历过程中，每当累加结果成为一个非正值时， 就应当将下一个元素作为潜在最大子数列的起始元素， 重新开始累加。
- 由于在累加过程中， 出现过的最大值都会被记录， 且每一个可能成为 最大子数列起始元素 的位置， 都会导致新一轮的累加， 这样就保证了答案搜索过程的完备性和正确性。
https://blog.csdn.net/the__apollo/article/details/77367534 从数学归纳法解释了 Kadane 算法。
题目中建议使用分治算法，思路是将数组不断二分，那么包含最大和的区间将分为这三种。
- 区间完全在 A[low,mid-1]
- 区间完全在 A[mid+1,high]
- 区间包含有 A[mid]
代码如下：
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
| class Solution {
public int maxSubArray(int[] nums) {
return divide(nums,0,nums.length-1);
}
public int divide(int[] nums, int left, int right){
if(left==right)
return nums[left];
if(left+1==right)
return Math.max(nums[left]+nums[right],Math.max(nums[left],nums[right]));
int mid=(left+right)/2;
int lmax=divide(nums,left,mid-1);
int rmax=divide(nums,mid+1,right);
int mmax=nums[mid];
int temp=mmax;
for(int i=mid-1;i>=left;i
temp+=nums[i];
mmax=mmax>temp?mmax:temp;
}
temp=mmax;
for(int i=mid+1;i<=right;i++){
temp+=nums[i];
mmax=mmax>temp?mmax:temp;
}
return Math.max(mmax,Math.max(lmax,rmax));
}
}
|