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 的大作中提到】
: 【 以下文字转载自 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 的大作中提到】
: 转载的就不模板了，呵呵。
: 好像很难。 O(N^2)还差不多；O(Nlog(N))也可能行；O(N)怎么搞？
:
: algorithm
|
t*****l
发帖数: 39 | 4 经典O(N)的算法
维持一个cumsum s, 从头加到尾，s<0就从0开始,记录中间s最大值
【在 N*****N 的大作中提到】
: Nlog(N)非常容易，呵呵。N高步出来 :(
|
N*****N
发帖数: 1605 | 5 好久没温习算法了 :(
不过这个还是不懂啊
【在 t*****l 的大作中提到】
: 经典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 的大作中提到】
: 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 的大作中提到】
: 【 以下文字转载自 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 的大作中提到】
: 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 的大作中提到】
: 转载的就不模板了，呵呵。
: 好像很难。 O(N^2)还差不多；O(Nlog(N))也可能行；O(N)怎么搞？
:
: algorithm
|
