leetcode-最大子序列和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

1：动态规划 O(n)

思路：

1
2
3
动态式：sum[i]:以i为结尾的最大子序列=Max{sum[i-1]+a[i],a[i]};

可以计算出以a[i]为结尾的最大子序列和，从中选出最大的。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSubArray(int[] nums) {
        //sum[i]:以a[i]为结尾的最大子序列和=max{sum[i-1]+a[i],a[i]}
        if(nums.length==0){
            return nums[0];
        }
        int max=nums[0];
        int maxPre=nums[0];
        for (int i = 1;i<nums.length;i++){
            int temp= nums[i]>(maxPre+nums[i])?nums[i]:(maxPre+nums[i]);
            maxPre=temp;
            max=max>temp?max:temp;
        }
        return max;
    }
}

2:分治法O(nLogn)

思路：

1
2
将数组分成两份，左边跟右边，那么最大的子序列 = Max {left,right,center}
递归结束条件：只有一个元素，return 该元素的值；

代码示例：

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
public int binarySubArray(int[] nums,int left,int right){
   
    if(left == right){
        return nums[left];
    }
    int center = (right +left )>>1;
    int leftMaxValue = binarySubArray(nums,left,center);//左边的最大子序列和
    int rightMaxValue = binarySubArray(nums,center+1,right);//右边的最大子序列和
    
    int centerLeftMaxValue=0;//从中心往左遍历找到的最大值（必须包含中心点）
    int centerRightMaxValue=0;//从中心往右遍历找到的最大值（必须包含中心点）
    
    int sumLeft=0;//用于记录遍历左侧的sum值
    int sumRight=0;//用于记录遍历右侧的sum值

    for(int i=center ;i>=left;i--){
        if(i==center){
            centerLeftMaxValue=nums[i];
            sumLeft=nums[i];
            continue;
        }
        sumLeft+=nums[i];
        centerLeftMaxValue=centerLeftMaxValue>sumLeft?centerLeftMaxValue:sumLeft;
    }
    
    for(int j =center+1;j<=right;j++){
        if(j==center+1){
            centerRightMaxValue=nums[j];
            sumRight=nums[j];
            continue;
        }
        sumRight+=nums[j];
        centerRightMaxValue=
            centerRightMaxValue>sumRight?centerRightMaxValue:sumRight;
    }        
    //返回Max{left,right,center}
    int sum = leftMaxValue>rightMaxValue?leftMaxValue:rightMaxValue;
    return sum>(centerLeftMaxValue+centerRightMaxValue)?sum:(centerLeftMaxValue+centerRightMaxValue);
}