題目: 給定一個(gè)整數(shù)數(shù)組 nums 资厉，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）兜辞，返回其最大和。
看到這題一開始想到的是用遞歸的方法:
假設(shè) 我們可以求出數(shù)組的最大序列, 我們就能得出數(shù)組兩個(gè)子序列的最大值, 然后與自身的和比較, 如果自身總和小于兩個(gè)子序列的最大值, 則返回子序列最大值為最終結(jié)果, 當(dāng)子序列長度不大于二, 則終止遞歸, 直接求出最大子序列返回
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
}
}
無奈遞歸的時(shí)間復(fù)雜度太高, 要通過必須要使用一個(gè)O(n)復(fù)雜度的方法
求助Google得到一個(gè)掃描法, 時(shí)間復(fù)雜度為O(n)
思路是這樣, 我們從數(shù)組的最左邊開始掃描, 將第一個(gè)元素設(shè)置為最大和, 以及子數(shù)組最左邊的元素
當(dāng)這個(gè)最左邊的元素為負(fù)數(shù)時(shí), 這是他對最大和是起負(fù)作用的, 我們就將下標(biāo)右移, 令下一個(gè)元素成為子數(shù)組其實(shí)元素, 并比較當(dāng)前最大值與下一個(gè)元素的大小, 如果下一個(gè)元素直接大于當(dāng)前最大值, 則重新賦值, 否則暫時(shí)保留. 直到我們找到一個(gè)元素為正數(shù), 這時(shí)候我們可以開始將其與下一個(gè)元素相加, 得到新的"current"子序列和, 如果這時(shí)子序列和為負(fù)數(shù), 說明他不會對接下來的序列擴(kuò)展起到正向效果, 那么我們先比較此時(shí)的最大和與之前的最大和的大小, 保存當(dāng)前掃描到的最大和, 然后棄掉現(xiàn)在的起始位置, 取下一個(gè)位置當(dāng)做起始位置, 開始掃描.
這種方式只需要一次掃描就可以得到結(jié)果, 但是真的不容易想出來...
代碼如下
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]
}
}
