標(biāo) 題: 微軟筆試題max subsequence sum
發(fā)信站: 飲水思源 (2005年11月07日11:05:23 星期一)
You are given an array of numbers which could be positive and negative. Please
write down a function to return the max subsequence sum from it.
Note: The sequence could start from any number within the array.
Sample: Array: -1, 7, -2, 5, -3
The max subsequence sum should be 10, by the subsequence 7, -2, 5.
大家討論一下，有哪些時間復(fù)雜度最低的算法。
--
※ 來源:·飲水思源 bbs.sjtu.edu.cn·[FROM: 219.228.107.45]
[回復(fù)本文] 發(fā)信人: BSR(bsr), 信區(qū): Algorithm
標(biāo) 題: Re: 微軟筆試題max subsequence sum
發(fā)信站: 飲水思源 (2005年11月07日12:27:18 星期一), 轉(zhuǎn)信
job 前天討論過了
o(n) 即可
【 在 oceanist (oceanist) 的大作中提到: 】
: You are given an array of numbers which could be positive and negative. Please
: write down a function to return the max subsequence sum from it.
: Note: The sequence could start from any number within the array.
: Sample: Array: -1, 7, -2, 5, -3
: The max subsequence sum should be 10, by the subsequence 7, -2, 5.
: 大家討論一下，有哪些時間復(fù)雜度最低的算法。
|