https://leetcode.cn/problems/maximum-subarray/
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
1
2
3
| 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
|
示例 2：
示例 3：
1
2
| 输入：nums = [5,4,-1,7,8]
输出：23
|
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
解题思路
- 遍历，前n个数相加，如果小于第n个数，则舍去前n-1个数，这样可以保证 前n个数最大
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func maxSubArray(nums []int) int {
if len(nums) == 0 {
return 0
}
max := nums[0]
sum := nums[0]
nums = nums[1:]
for _, v := range nums {
if sum+v > v {
sum += v
} else {
sum = v
}
if max < sum {
max = sum
}
}
return max
}
|