27
05/2015
[LeetCode] Maximum Subarray
Maximum Subarray
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.
解题思路：
题意为找出连续的和最大的子数组的和。可以有两种方法来做，动态规划以及分治法。
1、动态规划。求最值问题一般可以考虑动态规划的方法。d[i]表示子数组nums[k, i]的最大值，其中k>=0并且k<i。其递推公式为：
d[i] = nums[i], i==0 或者 d[i-1]<0 d[i] = nums[i] + d[i-1], 其他
然后返回d[]数组的最大值即可。这种方法的空间复杂度为O(n)，其实可以优化成O(1)的空间复杂度。时间复杂度为O(n)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
if(len<1){
return 0;
}
int d[len];
d[0]=nums[0];
int maxSum=nums[0];
for(int i=1; i<len; i++){
if(d[i-1]>0){
d[i]=nums[i]+d[i-1];
}else{
d[i]=nums[i];
}
maxSum = max(d[i], maxSum);
}
return maxSum;
}
};2、分治法。这种方法非常巧妙。对于一个数组nums[left, right]来说，nums[mid]是其中间元素。最大值子数组的分布无非三种情况：
（1）最大值子数组在mid前面
（2）最大值子数组在mid后边
（3）最大值子数组跨过mid
对于（1）（2），可以直接用递归来求得，对于（3），我们以mid向两边延伸找到最大的和。然后返回三种情况最大的一项即可。
空间复杂度为O(1)，时间复杂度为O(n)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
return maxSub(nums, 0, nums.size() - 1);
}
int maxSub(vector<int>& nums, int left, int right){
if(left>right){
return INT_MIN;
}
int mid = (left + right) / 2;
int lMax = maxSub(nums, left, mid - 1);
int rMax = maxSub(nums, mid + 1, right);
int sum = 0;
int lMaxSub = 0;
for(int i=mid - 1; i>=left; i--){
sum += nums[i];
lMaxSub = max(sum, lMaxSub);
}
int rMaxSub = 0;
sum = 0;
for(int i=mid + 1; i<=right; i++){
sum += nums[i];
rMaxSub = max(sum, rMaxSub);
}
return max(max(lMax, rMax), lMaxSub + rMaxSub + nums[mid]);
}
};转载请注明：康瑞部落 » [LeetCode] Maximum Subarray
0 条评论