求最大子列和

var nums = [1, -2, 2, -13, 6, -10, 3, 12]

/// O(n^3)
func maxSubSequenceSum1() {
    var maxSum = 0
    for i in 0..<nums.count {
        for j in i..<nums.count {
            var thisSum = 0
            for k in i...j {
                thisSum += nums[k]
            }
            if thisSum > maxSum {
                maxSum = thisSum
            }
        }
    }
    print(maxSum)
}

/// O(n^2)
func maxSubSequenceSum2() {
    var maxSum = 0
    for i in 0..<nums.count {
        var thisSum = 0
        for j in i..<nums.count {
            thisSum += nums[j]
            if thisSum > maxSum {
                maxSum = thisSum
            }
        }
    }
    print(maxSum)
}

/// O(n)
func maxSubSequenceSum3() {
    var maxSum = 0, thisSum = 0
    for i in 0..<nums.count {
        thisSum += nums[i]
        if thisSum > 0 {
            maxSum = thisSum
        } else { //如果thisSum小于0,则不可能使后面的部分和增大,抛弃.
            thisSum = 0
        }
    }
    print(maxSum)
}

maxSubSequenceSum1()
maxSubSequenceSum2()
maxSubSequenceSum3()

算法很重要呐 😄😄

–EOF–