[LeetCode] 53 Maximum contiguous subarray

正午 2020-01-05 AM 12℃ 0条

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
给定一个整数数组,寻找和最大的连续子数组的和。
例子:

Input: [-2,1,-3,4,-1,2,1,-5,4],

Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

解法一 暴力求解

遍历所有子数组求和,返回最大值,时间复杂度 O(n^2) 代码如下:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int m = nums[0];
        for(int i=0; i< nums.size(); i++){
            int subSum = 0;
            for(int j=i; j< nums.size(); j++){
                subSum += nums[j];
                m = max(m, subSum);
            }
        }
        return m;
    }
};

解法二 动态规划

动态规划,定义原问题,找到子问题和原问题的递推关系。
定义 maxSubArray(nums, i) 表示 nums 中以第 i 个元素结尾的连续子数组和的最大值,且

maxSubArray(nums, i) = nums[i] + (maxSubArray(nums, i-1) >0 ? maxSubArray(nums, i-1): 0 )

最终问题的答案就是从 maxSubArray(nums, 0), maxSumArray(nums, 1).... maxSumArray(nums, nums.size()-1) 中的最大值

代码实现如下

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> prefixSum(nums.size());
        prefixSum[0] = nums[0];
        int m = nums[0];

        int n = nums.size();
        for (int i=1; i< n; i++){
            prefixSum[i]= nums[i] +  (prefixSum[i-1] >0 ? prefixSum[i-1] :0 ) ;
            m = max(m, prefixSum[i]);
        }
        return m;
    }
};

上面的代码时间复杂度为 O(n) 空间复杂度为 O(n),空间复杂度可以进一步优化为 O(1)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int prefixSum = nums[0];
        int m = nums[0];
        int n = nums.size();
        for (int i=1; i< n; i++){
            prefixSum = nums[i] +  (prefixSum >0 ? prefixSum :0 ) ;
            m = max(m, prefixSum);
        }
        return m;
    }
};

解法三 分治法

原问题可以分解为三部分,如果 nums 的中间的元素的序号是 mid ,
第一部分左边数组的最大子数组和, maxSubArray(nums[:mid]),
第二部分右边数组的最大子数组和: maxSubArray(nums[mid:]),
第三部分包含中间元素的子数组和 maxAcrosseMid()

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxSubArraySection(nums, 0, nums.size()-1);
    }
    int maxAcrossMid(vector<int>& nums, int l, int mid, int r){
        int leftSum = INT_MIN;
        int sum = 0;
        for(int i=mid; i>=l ; i--){
            sum += nums[i];
            if (sum > leftSum){
                leftSum = sum;
            }
        }
        int rightSum = INT_MIN;
        sum = 0;
        for(int i=mid+1; i<= r; i++){
            sum += nums[i];
            if(sum > rightSum){
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
        
    }
    int maxSubArraySection(vector<int>& nums,int l, int r){
        if (l==r){
            return nums[l];
        }
        int mid = (l + r)/2; 
        return max(max(maxSubArraySection(nums, l, mid), maxSubArraySection(nums, mid+1, r)), maxAcrossMid(nums, l, mid, r));
    }
};
标签: LeetCode

非特殊说明,本博所有文章均为博主原创。

上一篇 没有了
下一篇 [LeetCode] 62. Unique Paths

评论