题目: 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
看到这题一开始想到的是用递归的方法:
假设 我们可以求出数组的最大序列, 我们就能得出数组两个子序列的最大值, 然后与自身的和比较, 如果自身总和小于两个子序列的最大值, 则返回子序列最大值为最终结果, 当子序列长度不大于二, 则终止递归, 直接求出最大子序列返回
func maxSubArray_1(_ nums: [Int]) -> Int {
if nums.count > 2 {
let count = 0
for num in nums {
count += num
}
let left = self.maxSubArray_1(Array(nums[0..<(nums.count - 1)]))
let right = self.maxSubArray_1(Array(nums[1...(nums.count - 1)]))
var max = left > right ? left : right
max = max > count ? max : count
return max
} else {
let left = nums[0]
let right = nums[nums.count - 1]
let count = 0
for num in nums {
count += num
}
var max = left > right ? left : right
max = max > count ? max : count
return max
}
}
无奈递归的时间复杂度太高, 要通过必须要使用一个O(n)复杂度的方法
求助Google得到一个扫描法, 时间复杂度为O(n)
思路是这样, 我们从数组的最左边开始扫描, 将第一个元素设置为最大和, 以及子数组最左边的元素
当这个最左边的元素为负数时, 这是他对最大和是起负作用的, 我们就将下标右移, 令下一个元素成为子数组其实元素, 并比较当前最大值与下一个元素的大小, 如果下一个元素直接大于当前最大值, 则重新赋值, 否则暂时保留. 直到我们找到一个元素为正数, 这时候我们可以开始将其与下一个元素相加, 得到新的"current"子序列和, 如果这时子序列和为负数, 说明他不会对接下来的序列扩展起到正向效果, 那么我们先比较此时的最大和与之前的最大和的大小, 保存当前扫描到的最大和, 然后弃掉现在的起始位置, 取下一个位置当做起始位置, 开始扫描.
这种方式只需要一次扫描就可以得到结果, 但是真的不容易想出来...
代码如下
func maxSubArray(_ nums: [Int]) -> Int {
if nums.count > 1 {
var current = nums[0]
var sum = nums[0]
for index in 1..<nums.count {
if current < 0 {
current = nums[index]
} else {
current += nums[index]
}
if current > sum {
sum = current
}
}
return sum
} else {
return nums[0]
}
}
