欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode问题53:最大的连续子数组和

程序员文章站 2022-06-02 20:13:37
...

问题描述

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.


解题策略

分治法

将数组折半,分成左部分和右部分。具有最大和的连续子数组要么在左部分中,要么在右部分中,要么两个部分都有(横跨中间)。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxSub(nums, 0, nums.size());
    }
    int maxSub(vector<int>& nums, int s, int e) {
        if (s >= e)
            return INT_MIN;
        int leftSum, midSum, rightSum;
        int mid = (s+e)/2;
        int sum = 0;
        int t1 = INT_MIN, t2 = INT_MIN;
        for (int i = mid-1; i >= s; --i) {
            sum += nums[i];
            t1 = max(sum, t1);
        }
        sum = 0;
        for (int i = mid+1; i < e; ++i) {
            sum += nums[i];
            t2 = max(sum, t2);
        }
        midSum = nums[mid];
        if (t1 > 0)
            midSum += t1;
        if (t2 > 0)
            midSum += t2;
        leftSum = maxSub(nums, s, mid);
        rightSum = maxSub(nums, mid+1, e);
        return max(midSum, max(leftSum, rightSum));
    }
};

动态规划1

dp defines as: maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element.

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

class Solution {
public:
    int maxSubArray(vector<int>& nums) { 
        int n = nums.size();
        if(n == 0) return 0;
        int result = INT_MIN; 
        int pre = 0;
        for(int i = 0; i < n; ++i){
            pre = nums[i] + max(pre, 0);
            result = max(result, pre);
        }
        return result;
    }
};

  1. 代码引用自LeetCode,作者不详
相关标签: n'