描述
给定一个序列(至少含有 1 个数),从该序列中寻找一个连续的子序列,使得子序列的和最大。
例如,给定序列 [-2,1,-3,4,-1,2,1,-5,4],
连续子序列 [4,-1,2,1] 的和最大,为 6。
我 v1.0
测试结果如下:
本地运行时间为14.7s,说明我的方法太粗暴了。应该寻找更好的算法。
我 优化后v1.1。优化方案,去掉sums数组,节省空间。但时间复杂度仍然不变。
仍然只通过200/202测试用例,仍然超出时间限制。但本地运行时间为8.3s。有进步。
别人,分治法。时间复杂度O(NlogN)
将输入的序列分成两部分,这个时候有三种情况。
1)最大子序列在左半部分
2)最大子序列在右半部分
3)最大子序列跨越左右部分。
前两种情况通过递归求解,第三种情况可以通过。
分治法代码大概如下,emmm。。。目前还没有完全理解。
动态规划算法,时间复杂度为O(n)。
分析:寻找最优子结构。
Oh!My god!!! !!!!!!!!运行只花了0.2s!!!!!!!!!!!!!!!这也太强了吧!!
优化后,运行时间0.1s.
其中
sum += nums[i]
必须紧挨。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。