53. Maximum Subarray （Kadane算法 / 动态规划 / 分治法）
53. Maximum Subarray （Kadane算法 / 动态规划 / 分治法）
Maximum Subarray
【题目】
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.
【分析】
这是一道非常简单的算法题，但是实现的方法却有很多种。在本篇文章中，博主想介绍三种巧妙的方法，这三种方法在面试和刷题过程中有非常广泛的应用。
方法一：Kadane算法
算法描述：
- 遍历该数组， 在遍历过程中， 将遍历到的元素依次累加起来， 当累加结果小于或等于0时， 从下一个元素开始，重新开始累加。
- 累加过程中， 要用一个变量(max_so_far)记录所获得过的最大值。
- 一次遍历之后， 变量 max_so_far 中存储的即为最大子片段的和值。
Java实现代码如下：
public class MaximumSubarray {
public int maxSubArray(int[] nums) {
int maxEndHere = 0;
int maxSoFar = 0;
for (int i = 0; i < nums.length; i++) {
maxEndHere += nums[i];
if (maxEndHere < 0) {
maxEndHere = 0;
}
if (maxSoFar < maxEndHere) {
maxSoFar = maxEndHere;
}
}
return maxSoFar;
}理解此算法的关键在于:
- 最大子片段中不可能包含求和值为负的前缀。 例如 【-2， 1，4】 必然不能是最大子数列， 因为去掉值为负的前缀后【-2，1】， 可以得到一个更大的子数列 【4】、
- 所以在遍历过程中，每当累加结果成为一个非正值时， 就应当将下一个元素作为潜在最大子数列的起始元素， 重新开始累加。
- 由于在累加过程中， 出现过的最大值都会被记录， 且每一个可能成为 最大子数列起始元素 的位置， 都会导致新一轮的累加， 这样就保证了答案搜索过程的完备性和正确性。
方法二：DP（动态规划）
基本思路是这样的，在每一步，我们维护两个变量，一个是全局最优，就是到当前元素为止最优的解是，一个是局部最优，就是必须包含当前元素的最优的解。接下来说说动态规划的递推式（这是动态规划最重要的步骤，递归式出来了，基本上代码框架也就出来了）。假设我们已知第i步的global[i]（全局最优）和local[i]（局部最优），那么第i+1步的表达式是：
- local[i+1]=Math.max(A[i], local[i]+A[i])，就是局部最优是一定要包含当前元素，所以不然就是上一步的局部最优local[i]+当前元素A[i]（因为local[i]一定包含第i个元素，所以不违反条件），但是如果local[i]是负的，那么加上他就不如不需要的，所以不然就是直接用A[i]；
- global[i+1]=Math(local[i+1],global[i])，有了当前一步的局部最优，那么全局最优就是当前的局部最优或者还是原来的全局最优（所有情况都会被涵盖进来，因为最优的解如果不包含当前元素，那么前面会被维护在全局最优里面，如果包含当前元素，那么就是这个局部最优）。
Java代码实现如下：
class Solution {
//Dp
public int maxSubArray(int[] nums) {
int maxLocal = nums[0];
int global = nums[0];
for (int i = 1; i < nums.length; ++i) {
maxLocal = Math.max(nums[i], nums[i] + maxLocal);
global = Math.max(global, maxLocal);
}
return global;
}
}方法三：分治法
将数组均分为两个部分，那么最大子数组会存在于：
- 左侧数组的最大子数组
- 右侧数组的最大子数组
- 左侧数组的以右侧边界为边界的最大子数组+右侧数组的以左侧边界为边界的最大子数组
假设数组下标有效范围是l到r,将数组分为左半部分下标为（l，mid-1）和右半部分下标为(mid+1，r)以及中间元素下标为mid，接下来递归求出左半部分的最大子序和：left=helper(nums,l,mid-1); 右半部分最大子序和right=helper(nums,mid+1,r);
接下来再将左半部分右边界，右半部分左边界以及中间元素nums[mid]整合，用了两个循环，先整合左半部分右边界和中间值，再将整合结果与右半部分左边界整合得到整合以后的最大子序和max_num，最后返回max_num，left,right的最大值即是要求的最大子序和。
代码实现如下：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size()==0)return 0;
return helper(nums,0,nums.size()-1);
}
int helper(vector<int>& nums,int l,int r){
if(l>r)return INT_MIN;//注意此处不是返回0，比如｛-2，-1｝，分治以后变为左中右n｛｝，-1，｛-2｝三部分。左半部分｛｝应返回INT_MIN，
//因为还要和右半部分的返回值进行比较,最终正确结果返回-1。若左半部分返回0，0>-2,且大于左中右的最大组合值（-1），最终结果返回0，出错
if(l==r)return nums[l];
int mid=(l+r)/2;
int left=helper(nums,l,mid-1);
int right=helper(nums,mid+1,r);
int t=nums[mid];
int max_num=nums[mid];
for(int i=mid-1;i>=l;i--){
t+=nums[i];
max_num=max(max_num,t);
}
t=max_num;
for(int i=mid+1;i<=r;i++){
t+=nums[i];
max_num=max(max_num,t);
}
return max(max(left,right),max_num);
}
};腾讯云开发者
