求最大子列和

栏目: JavaScript · 发布时间: 6年前

内容简介:算法很重要呐 :smile::smile:
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()

算法很重要呐 :smile::smile:

--EFO--


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Python标准库

Python标准库

Doug Hellmann / 刘炽 / 机械工业出版社华章公司 / 2012-6-15 / 139.00元

本书由资深Python专家亲自执笔,Python语言的核心开发人员作序推荐,权威性毋庸置疑。 对于程序员而言,标准库与语言本身同样重要,它好比一个百宝箱,能为各种常见的任务提供完美的解决方案,所以本书是所有Python程序员都必备的工具书!本书以案例驱动的方式讲解了标准库中一百多个模块的使用方法(如何工作)和工作原理(为什么要这样工作),比标准库的官方文档更容易理解(一个简单的示例比一份手册......一起来看看 《Python标准库》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

在线进制转换器
在线进制转换器

各进制数互转换器

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试