问题

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

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

方法一(贪心)

我们从头开始求子序列和，当子序列的和<0的时候，那该子序列就不能和接下来的数组合在一起了，因为会使接下来的序列和变小。所以新的子序列要从下一个数字开始。或者也可以说，当前面的子序列和<0的时候，新的子序列要从当前元素开始。代码如下：

  1. impl Solution {
  2.     pub fn max_sub_array(nums: Vec<i32>) -> i32 {
  3.         let mut res = std::i32::MIN;
  4.         let mut sum = 0;
  5.         for num in nums {
  6.             if sum < 0 {
  7.                 sum = num;
  8.             } else {
  9.                 sum += num;
  10.             }
  11.             res = std::cmp::max(res, sum);
  12.         }
  14.         res
  15.     }
  16. }

方法二(动态规划)

1、定义子问题
用最大子序列和 - 图1表示 以 nums[k] 结尾的最大子序列和，则最终所求的结果为最大子序列和 - 图2。
2、写出递推关系

  • 最大子序列和 - 图3
  • 最大子序列和 - 图4

3、确定dp数组计算顺序
从做到右即可
4、编码

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        if nums.len() < 1 {
            return 0;
        }

        let mut dp = vec![0_i32; nums.len()];
        dp[0] = nums[0];
        let mut res = dp[0];
        for i in 1..nums.len() {
            dp[i] = std::cmp::max(dp[i-1], 0) + nums[i];
            res = std::cmp::max(res, dp[i]);
        }

        res
    }
}

/// dp数组可以用一个变量代替，就相当于贪心算法，不过思路不同

方法三(分治)

。。。