one algorithm question - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>BrainTeaser - 大脑工作室

one algorithm question

one algorithm question# BrainTeaser - 大脑工作室

N*N2007-05-04 07:05

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*N2007-05-04 07:05

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*N2007-05-04 07:05

3 楼

Nlog(N)非常容易，呵呵。N高步出来 :(

【在 N*****N 的大作中提到】

: 转载的就不模板了，呵呵。
: 好像很难。 O(N^2)还差不多；O(Nlog(N))也可能行；O(N)怎么搞？
:
: algorithm

t*l2007-05-04 07:05

4 楼

经典O(N)的算法
维持一个cumsum s, 从头加到尾，s<0就从0开始,记录中间s最大值

【在 N*****N 的大作中提到】

: Nlog(N)非常容易，呵呵。N高步出来 :(

N*N2007-05-04 07:05

5 楼

好久没温习算法了 :(
不过这个还是不懂啊

【在 t*****l 的大作中提到】

: 经典O(N)的算法
: 维持一个cumsum s, 从头加到尾，s<0就从0开始,记录中间s最大值

t*l2007-05-04 07:05

6 楼

http://www.cprogramming.com/challenges/solutions/array_sum.html

【在 N*****N 的大作中提到】

: 好久没温习算法了 :(
: 不过这个还是不懂啊

N*N2007-05-04 07:05

7 楼

kao，太牛了，呵呵

【在 t*****l 的大作中提到】

: http://www.cprogramming.com/challenges/solutions/array_sum.html

o*r2007-05-04 07:05

8 楼

algorithm
check the algorithm for DNA local alignment. It could be translated into
this problem and is O(N)

【在 N*****N 的大作中提到】

: kao，太牛了，呵呵

i*c2007-05-04 07:05

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 的大作中提到】

i*c2007-05-04 07:05

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)
: