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

[azl397985856]

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

首先我们来明确一下题意。

• 题目说的子数组是连续的
• 题目只需要求和，不需要返回子数组的具体位置。
• 数组中的元素是整数，但是可能是正数，负数和0。
• 子序列的最小长度为1。

比如：

• 对于数组 [1, -2, 3, 5, -3, 2], 应该返回 3 + 5 = 8
• 对于数组 [0, -2, 3, 5, -1, 2], 应该返回 3 + 5 + -1 + 2 = 9
• 对于数组 [-9, -2, -3, -5, -3], 应该返回 -2

[snowan]

我试试这个吧.. 😁
认领

[azl397985856]

我试试这个吧..
认领

done

[xiongcaihu]

``` .js
/**

• @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;

};
```

[azl397985856]

我试试这个吧.. 😁
认领

leetcode 原题 53号题目

[raof01]

分治法：

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;
    }
};