N*****N 发帖数: 1605 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: sdlx (sdlx), 信区: JobHunting
标 题: one algorithm question
发信站: BBS 未名空间站 (Fri May 4 22:59:34 2007)
You're given an array containing both positive and negative integers
and required to find the sub-array with the largest sum (O(N)
anyone can point me the right solution? I could not find it in my algorithm
book.
Thanks in advance !!! |
N*****N 发帖数: 1605 | 2 转载的就不模板了,呵呵。
好像很难。 O(N^2)还差不多;O(Nlog(N))也可能行;O(N)怎么搞?
algorithm
【在 N*****N 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: sdlx (sdlx), 信区: JobHunting : 标 题: one algorithm question : 发信站: BBS 未名空间站 (Fri May 4 22:59:34 2007) : You're given an array containing both positive and negative integers : and required to find the sub-array with the largest sum (O(N) : anyone can point me the right solution? I could not find it in my algorithm : book. : Thanks in advance !!!
|
N*****N 发帖数: 1605 | 3 Nlog(N)非常容易,呵呵。N高步出来 :(
【在 N*****N 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 转载的就不模板了,呵呵。 : 好像很难。 O(N^2)还差不多;O(Nlog(N))也可能行;O(N)怎么搞? : : algorithm
|
t*****l 发帖数: 39 | 4 经典O(N)的算法
维持一个cumsum s, 从头加到尾,s<0就从0开始,记录中间s最大值
【在 N*****N 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Nlog(N)非常容易,呵呵。N高步出来 :(
|
N*****N 发帖数: 1605 | 5 好久没温习算法了 :(
不过这个还是不懂啊
【在 t*****l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 经典O(N)的算法 : 维持一个cumsum s, 从头加到尾,s<0就从0开始,记录中间s最大值
|
t*****l 发帖数: 39 | |
N*****N 发帖数: 1605 | |
o********r 发帖数: 775 | 8
algorithm
check the algorithm for DNA local alignment. It could be translated into
this problem and is O(N)
【在 N*****N 的大作中提到】![](/moin_static193/solenoid/img/up.png) : kao,太牛了,呵呵
|
i**********c 发帖数: 22 | 9 dynamic programming,
each step you record two max values:
1) the max so far
2) the max from the end
and 1>=2>=0
during each step you compare 2+the new end against 1 to decide new 1,
and compare 2+new end against 2 to decide new 2,
the cost is O(1),
so the total cost is O(n)
algorithm
【在 N*****N 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: sdlx (sdlx), 信区: JobHunting : 标 题: one algorithm question : 发信站: BBS 未名空间站 (Fri May 4 22:59:34 2007) : You're given an array containing both positive and negative integers : and required to find the sub-array with the largest sum (O(N) : anyone can point me the right solution? I could not find it in my algorithm : book. : Thanks in advance !!!
|
i**********c 发帖数: 22 | 10 ft, late,
peng myself
【在 i**********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : dynamic programming, : each step you record two max values: : 1) the max so far : 2) the max from the end : and 1>=2>=0 : during each step you compare 2+the new end against 1 to decide new 1, : and compare 2+new end against 2 to decide new 2, : the cost is O(1), : so the total cost is O(n) :
|
h*****0 发帖数: 4889 | 11 找到最大和与最小和,二者之间即是
【在 N*****N 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 转载的就不模板了,呵呵。 : 好像很难。 O(N^2)还差不多;O(Nlog(N))也可能行;O(N)怎么搞? : : algorithm
|