【leetcode】53. Maximum Subarray

发表于 | 分类于 | 浏览 次
字数统计: 681 | 阅读时长 ≈ 3

题目

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. 遍历，复杂度O(n^2)
  2. 分治法，《算法导论》第四章讲过

把数组看作A[low..high]，利用分治策略，将数组划分为两个规模尽量相等的子数组，找到数组的中央位置，A[mid]，然后考虑求解两个子数组A[low..mid]和A[mid+1..high]。那么子数组A[i..j]所有的情况共有以下三种：

那么我们可以递归的求解A[low..mid]和A[mid+1..high]的最大子数组，因为这两个子问题仍是最大数组问题，只是规模更小。因此剩下的工作就是寻找跨越中点的最大子数组，然后在三者中选取最大者。

算法复杂度：O(nlogn)

  1. 动态规划

当从头遍历数组元素时，对于数组中的任何一个整数有以下两种选择：

加入之前的subArray；自己另起一个新的subArray

  • 当之前subArray 的总和大于 0 时，我们认为 其对后续结果是有贡献的，这种情况下，我们选择加入之前的subArray
  • 当之前subArray 的总和小于等于0时，我们认为其对后续结果是没有贡献的，这种情况下，我们选择以当前数字开始，另起一个subArray

设状态f(j) 表示 以 nums[j] 为结尾的最大连续子序列的和，则状态转移方程如下：

时间复杂度O(n)

代码：

//分治法
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return findMaxSubArray(nums,0,nums.size()-1);
    }
private:
    int maxArrayAcrossMid(vector<int>& numsIn, int low, int high) {//求跨越中点的最大子数组数字和
    int len = (high - low) / 2;
    int mid = (high + low) / 2;
    int maxnum = numsIn[mid];
    int maxnumtemp = numsIn[mid];
    for (int i = mid - 1; i >= low; i--) {//计算左边最大子数组
        maxnumtemp += numsIn[i];
        if (maxnumtemp > maxnum)
            maxnum = maxnumtemp;
    }
    maxnumtemp = maxnum;
    for (int i = mid + 1; i <= high; i++) {//计算右边最大子数组
        maxnumtemp += numsIn[i];
        if (maxnumtemp > maxnum)
            maxnum = maxnumtemp;
    }
    return maxnum;
}
int findMaxSubArray(vector<int>& nums, int low, int high) {//递归调用求解最大子数组
    int mid = (low + high) / 2;
    int maxSum = nums[mid];
    int acrossmid = 0;
    int leftmax = 0;
    int rightmax = 0;
    if (low == high) {
        return maxSum;
    }
    else {
        acrossmid = maxArrayAcrossMid(nums, low, high);
        leftmax = findMaxSubArray(nums, low, mid);
        rightmax = findMaxSubArray(nums, mid + 1, high);
    }
    if (acrossmid >= leftmax && acrossmid >= rightmax) return acrossmid;
    if (leftmax >= acrossmid && leftmax >= rightmax) return leftmax;
    else return rightmax;
}
    
};
//动态规划
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
            int maxnum = nums[0];
    int numtemp = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (numtemp < 0) numtemp = 0;
        numtemp += nums[i];
        if (numtemp > maxnum) {
            maxnum = numtemp;
        }
    }
        return maxnum;
    }
};

结果