最大子序和

最后更新于:2022-04-02 04:23:01

[TOC] ## 最大子序和 示例 1: ``` 输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。 ``` 示例 2: ``` 输入:nums = [1] 输出:1 ``` ## 实现 一种简单理解实现 ``` func maxSubArray(nums []int) int { if len(nums) < 2 { return nums[0] } max := nums[0] lastMax := nums[0] for i := 1; i < len(nums); i++ { n := nums[i] if tmp := n + max; tmp > n { max = tmp } else { max = n } } return lastMax } ``` 利用 nums[i] 保存 lastMax 的值 ``` func maxSubArray(nums []int) int { if len(nums) < 2 { return nums[0] } max := nums[0] for i := 1; i < len(nums); i++ { if nums[i] < nums[i]+nums[i-1] { nums[i] = nums[i] + nums[i-1] } if nums[i] > max { max = nums[i] } } return max } ```
';