給定一個(gè)整數(shù)數(shù)組 nums 咳促，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和及舍。
進(jìn)階: 如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法醉蚁，嘗試使用更為精妙的 分治法 求解。
摘一個(gè)示例做個(gè)說明.
示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大盒蟆，為 6 踏烙。
條件分析:
- 最大和的連續(xù)子數(shù)組
解決思路1:
- 根據(jù)分析1,說明數(shù)據(jù)有正數(shù)有負(fù)數(shù).當(dāng)前最大和就是前面到當(dāng)前位置中和最大的數(shù),先找第一個(gè),然后和后面相加的進(jìn)行比較.
采用循環(huán)判斷存儲(chǔ),然后當(dāng)前和與之前和進(jìn)行找最大值.最大的那個(gè)就是最后返回的最大和.
func maxSubArray(_ nums: [Int]) -> Int {
var dp = [Int](repeating: 0, count: nums.count)
dp[0] = nums[0]
var maxSum = dp[0]
for i in 1..<nums.count {
dp[i] = max(dp[i-1]+nums[i],nums[i])
maxSum = max(dp[i], maxSum)
}
return maxSum
}
測(cè)試用例:
let num = [1]
let num = [-1]
let num = [0]
let num = [1,2,3,-3,4,7,-2,9,8,-10,2,13,0]
考察要點(diǎn):
- 數(shù)組
- 分治
- 動(dòng)態(tài)規(guī)劃
