Maximum problem - 推理遊戲

Poppy avatar
By Poppy
at 2004-11-18T17:22

Table of Contents

※ 引述《joyboytoy (亂來 XD)》之銘言：

: 這種解法的效率在於, 之前算過的東西不用重算
: 譬如c1的値不必去作X1+X2+X3+X4, 而只要 b1+X4 即可
: 等到數列變長, 節省的計算也就越多
: 長度為n的數列只需要 (n-1)^2/2 次的相加
: 以上是用dynamic programming去作的
: 不過不知道有沒有更快的解法 @__@


你的解法time complexity 為 O(n^2) , 效率不是說很好

其實你可以根據前面 citronrisky 板友的想法稍加改變

即可找出 linear 的解法

--

All Comments

古老的問題(改)

Oscar avatar
By Oscar
at 2004-11-18T13:19
老師與兩學生甲乙進行一項遊戲: 首先,甲乙分別在紙上寫下一個正整數交給老師 接著老師在黑板上寫上兩個正整數: 一個是兩學生所寫數字的和,一個是老師自己亂寫的數字 甲乙知道黑板上的兩數字中有一個是甲乙兩人的數字和,但是不知道是哪一個 假設甲乙兩人非常聰明且誠實 甲乙也知道對方非常聰明且誠實 接著老師問 ...

Sandy avatar
By Sandy
at 2004-11-18T10:15
剛剛朋友問我的 有一個大力士要過橋 他有一百公斤重 還有三顆一百公斤的球要搬過去 可是橋只能承受三百公斤重 他要怎麼過去?? 總覺得這題比較像腦筋急轉彎而不是推理 = =.... -- 三餐不旺 福用音樂 成名在旺 福搖直上 休假無 ...

Maximum problem

Olive avatar
By Olive
at 2004-11-18T05:18
※ 引述《Redsuns (ZZZzzz...)》之銘言： : 1. 基本題 : 假設有一數列 {X1,X2,X3,X4,.....Xn} : 請找出一演算法能夠找出一連續的子數列,使他們的和為最大值 : 例: {2,-4,2,5,-2,3,4,-5,3,1} 則其子數列{2,5,-2,3,4}有最大的和 ...

Maximum problem

Valerie avatar
By Valerie
at 2004-11-17T20:36
1. 基本題 假設有一數列 {X1,X2,X3,X4,.....Xn} 請找出一演算法能夠找出一連續的子數列,使他們的和為最大值 例: {2,-4,2,5,-2,3,4,-5,3,1} 則其子數列{2,5,-2,3,4}有最大的和 2. 進階題 題目大致一樣,要找一連續的子數列,使他們的乘積 ...

Re: 推理小謎題

Harry avatar
By Harry
at 2004-11-17T17:31
※ 引述《lahair (想學游泳的熊)》之銘言： : ※ 引述《citronrisky (瑞士基)》之銘言： : : b) : : 有四名登山客被大雪困在山上的小屋中, : : 他們在體力透支的情況下, : : 如果睡著了, 可能就會失溫而死, : : 於是他們各佔據屋子的一角, : : A沿著第一個邊走到 ...