求取数组中最大连续子序列和，例如给定数组为 A = [1， 3， -2， 4， -5]，则最大连续子序列和为 6，即 1 + 3 +（-2）+ 4 = 6。去<

<div class="highlight highlight-source-js notranslate position-relative overflow-auto" dir="auto" da

分治法： <div class="highlight highlight-source-c++ notranslate position-relative over

【每日一题】- 2019-08-15 - 最大子序列和问题 about leetcode HOT 5 CLOSED

azl397985856 commented on May 5, 2024

【每日一题】- 2019-08-15 - 最大子序列和问题

from leetcode.

Comments (5)

snowan commented on May 5, 2024 2

我试试这个吧.. 😁
认领

from leetcode.

azl397985856 commented on May 5, 2024

我试试这个吧..
认领

done

from leetcode.

xiongcaihu commented on May 5, 2024

/**
 * @param {number[]} nums
 * @return {number}
 * 
 * F(n) = F(n-1) + nums[n] when F(n-1)>0
 * or
 * F(n) = nums[n] when F(n-1)<=0
 */
// var maxSubArray = function (nums) {
//     var dp = [nums[0]];
//     for (var i = 1; i < nums.length; i++) {
//         if (dp[i - 1] > 0) {
//             dp[i] = dp[i - 1] + nums[i];
//         } else {
//             dp[i] = nums[i];
//         }
//     }

//     return Math.max(...dp);
// };
var maxSubArray = function (nums) {
    var dp = nums[0],
        max = dp;
    for (var i = 1; i < nums.length; i++) {
        if (dp > 0) {
            dp += nums[i]
        } else {
            dp = nums[i];
        }
        max = Math.max(dp, max);
    }

    return max;
};

from leetcode.

azl397985856 commented on May 5, 2024

我试试这个吧.. 😁
认领

leetcode 原题 53号题目

from leetcode.

raof01 commented on May 5, 2024

分治法：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        auto l=0,r=0,m=0,s=0;
        helper(nums, 0, nums.size() - 1, l, r, m, s);
        return m;
    }
private:
    void helper(vector<int>& v, size_t s, size_t e, int& l, int& r, int& m, int& sum) {
        if (s == e) {
            l = r = m = sum = v[s];
            return;
        }
        auto mid = s + (e - s) / 2;
        int l1, r1, m1, s1, l2, r2, m2, s2;
        helper(v, s, mid, l1, r1, m1, s1);
        helper(v, mid + 1, e, l2, r2, m2, s2);
        l = max(l1, s1 + l2);
        r = max(r2, s2 + r1);
        m = max(max(m1, m2), r1 + l2);
        sum = s1 + s2;
    }
};