题目:输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为{3,10,-4,7,2}，因此输出为该子数组的和18.
核心代码:
<pre><code>`
func findGreatestSumOfSubArray(arr:[Int]) -> Int {
var maxSum:Int = 0
var currentSum:Int = 0
for i in 0..<arr.count {
currentSum += arr[i]
if currentSum > maxSum {
maxSum = currentSum
}
if currentSum < 0 { //如果相加为负数,将CurSum置空
currentSum = 0
}
}
return maxSum
}`</code></pre>
测试代码:
<pre><code>`
var maxSum:MaxSum = MaxSum()
var arr:[Int] = [1,-2,3,10,-4,7,2,-5]
var sum = maxSum.findGreatestSumOfSubArray(arr: arr)
print("FlyElephant-连续子数组最大的和--(sum)")`</code></pre>
