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

leetcode【53】Maximum Subarray

程序员文章站 2022-07-15 19:48:38
...

问题描述:

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.

源码:

从上到下,分别是分治法 ,举例分析法和动态规划法

leetcode【53】Maximum Subarray

动态规划法:

最简单明了的方法,f(i)表示以i结尾的字串的和的最大值。这里用sum就行了。

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

剑指offerp218页(举例分析法):

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;
        int cur = 0;
        int max_val = INT_MIN;
        for(int i=0; i<nums.size(); i++){
            if(cur<=0){
                cur = nums[i];
            }
            else{
                cur += nums[i];
            }
            max_val = max_val>cur? max_val: cur;
        }
        return max_val;
    }
};

分治法:

class Solution {
public:
    int solve(int left, int right, vector<int>& nums){
        if(left >= right)   return nums[left];
        int mid = (left + right) / 2;
        int tmp_res = max(solve(left, mid, nums), solve(mid+1, right, nums));
        
        int res_right=0, res_left=0;
        int r_max=nums[mid+1], l_max=nums[mid];
        
        for(int i=mid; i>=left; i--){
            res_left += nums[i];
            l_max = max(l_max, res_left);
        }
        for(int j=mid+1; j<=right; j++){
            res_right += nums[j];
            r_max = max(r_max, res_right);
        }
        return r_max + l_max > tmp_res? r_max + l_max : tmp_res;
    }
    
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==0)  return 0;
        return solve(0, nums.size()-1, nums);
    }
};