1
2
3

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设 dp[i]: 以nums[i]为尾的最大连续子数组和
    /// 2. 则 dp[i] = max(dp[i-1]+nums[i], nums[i])
    /// 3. 初始条件: dp[0] = nums[0]
    /// 4. 目标值: max(dp[i])
    pub fn max_sub_array1(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut dp = vec![0; n];
        dp[0] = nums[0];
        let mut res = dp[0];
        for i in 1..n {
            dp[i] = nums[i].max(dp[i - 1] + nums[i]);
            res = res.max(dp[i]);
        }

        res
    }

    /// - 优化: dp[i]只和dp[i-1]相关, 可用两个整形变量代替;
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut dp = nums[0];
        let mut res = dp;
        for i in 1..n {
            dp = nums[i].max(dp + nums[i]);
            res = res.max(dp);
        }

        res
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        passedSum = nums[0]
        maxSum = passedSum
        for current in nums[1:]:
            if passedSum > 0:
                passedSum += current
                maxSum = max(maxSum, passedSum)
            else:
                maxSum = max(maxSum, current, passedSum)
                passedSum = current

        return maxSum