leetcode 53. Maximum Subarray 최대 연속 하위 시퀀스 및

3838 단어 leetcode
최대 연속 하위 시퀀스 및
leetcode 53. Maximum Subarray
동적 기획
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> d(nums.size(),0);
        d[0]=nums[0];
        for(size_t i=1;i1]+nums[i]);
        int maxsum=d[0];
        for(size_t i=1;ireturn maxsum;
    }
};

분치하다
원시 연결
mx (largest sum of this subarray), 
lmx(largest sum starting from the left most element), 
rmx(largest sum ending with the right most element), 
sum(the sum of the total subarray). 
class Solution {
public:
    void maxSubArray(vector<int>& nums, int l, int r, int& mx, int& lmx, int& rmx, int& sum) {
        if (l == r) {
            mx = lmx = rmx = sum = nums[l];
        }
        else {
            int m = (l + r) / 2;
            int mx1, lmx1, rmx1, sum1;
            int mx2, lmx2, rmx2, sum2;
            maxSubArray(nums, l, m, mx1, lmx1, rmx1, sum1);
            maxSubArray(nums, m + 1, r, mx2, lmx2, rmx2, sum2);
            mx = max(max(mx1, mx2), rmx1 + lmx2);
            lmx = max(lmx1, sum1 + lmx2);
            rmx = max(rmx2, sum2 + rmx1);
            sum = sum1 + sum2;
        }
    }
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        int mx, lmx, rmx, sum;
        maxSubArray(nums, 0, nums.size() - 1, mx, lmx, rmx, sum);
        return mx;
    }
};

좋은 웹페이지 즐겨찾기