数组中n个整数数组，求n个数的最大连续子序列和，数组中元素有正数和负数~

穷举

遍历所有的子序列和，比较暴力,时间复杂度O(n^3)

func maxSequenceSum1(data:[Int]) -> Int {
    var maxSum = 0
    for i in 0..<data.count {
        for j in i..<data.count {
            var currentSum = 0
            //求i..j之间的子序列和
            for k in i...j {
                currentSum += data[k]
            }
            if maxSum < currentSum {
                maxSum = currentSum
            }
        }
    }
    return maxSum
}

穷举简化

穷举的过程中发现，如果计算data[0]~data[3] ，data[0]~data[4]发现，我们只需要用上一次的值加上data[4]即可，时间复杂度为O(n^2)

func maxSequenceSum2(data:[Int]) -> Int {
    var maxSum = 0
    for i in 0..<data.count {
        var currentSum = 0
        for j in i..<data.count {
            currentSum += data[j]
            if maxSum < currentSum {
                maxSum = currentSum
            }
        }
    }
    return maxSum
}

递归

数组中最大的子序列和出现在三个地方，左半部分，中间部分和右半部分，然后对三部分的值进行比较可以求出最大子序列和:

func maxSequenceSum3(data:[Int],left:Int,right:Int) -> Int {
    if left == right {
        if data[left] > 0 {
            return data[left]
        } else {
            return 0
        }
    }
    
    let center:Int = (left+right)/2
    let leftResult = maxSequenceSum3(data, left: left, right: center)
    let rightResult = maxSequenceSum3(data, left: center+1, right: right)
    
    // 左半部分包含子序列的和
    var maxleftSum = 0
    var leftSum = 0
    for i in center.stride(to:left, by: -1) {
        leftSum += data[i]
        if maxleftSum < leftSum {
            maxleftSum = leftSum
        }
    }
    var rightSum = 0
    let begin = center+1
    var maxRightSum = 0
    for j in begin...right {
        rightSum += data[j]
        if maxRightSum < rightSum {
            maxRightSum = rightSum
        }
    }
    let middleResult = maxleftSum + maxRightSum
    let result = leftResult > rightResult ? leftResult : rightResult
    return result > middleResult ? result : middleResult
}

最佳

遍历数组，如果数组相加的时候小于0，将和设置为0，否则一直相加，时间复杂度为O(n)

func maxSequenceSum4(data:[Int])->Int {
    var sum = 0
    var maxSum = 0
    for index in 0..<data.count {
        sum += data[index]
        if sum < 0 {
            sum = 0
        } else if maxSum < sum {
            maxSum = sum
        }
    }
    return maxSum
}

测试

var dataSource:[Int] = [2,-4,5,7,-1,6]
var result1 = maxSequenceSum1(dataSource)
var result2 = maxSequenceSum2(dataSource)
var result3 = maxSequenceSum3(dataSource, left: 0, right: dataSource.count-1)
var result4 = maxSequenceSum4(dataSource)
print("FlyElephant:--\(result1)--\(result2)--\(result3)--\(result4)")