[問題] 求數字和最大的區間

[cory8249 (Cory)]

各位好:


小弟新手寫題目卡關

麻請各位多多幫忙了




題目:http://judge.tnfsh.tn.edu.tw:8080/ShowProblem?problemid=b003

給你一串數字

要找出其中數字和最大的連續區間，求其和

範例:

-1 2 3 -2 1

答案是從 2+3 = 5


Code:

1.TLE的原始暴力解法: http://www.pastie.org/2059471

2.答案不太正確的去頭去尾法:http://www.pastie.org/2059080

3.不知道有沒有改善的合併計算法:http://www.pastie.org/2059490


第一種解法的答案應該是正確的，但是數量太多就會超過時間限制 TLE


第二種是我另外想的方法，但是不太正確

因為判斷的過程中可能會捨棄掉最大值

Ex :   99 -100 1 1 1 1 -2

這樣子答案應該只要取99就好

而不是程式跑出來的 4


第三種算法

把連續正值、連續負值都先個別加起來

然後 ... 重新整合一個正負相隔的數列

這樣子不知道有沒有比較好 ??




感謝各位耐心看完亂七八糟的程式碼

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.255.23.104
→ suhorng:http://aikosenoo.pixnet.net/blog/post/7442660
原來如此....

感謝



只要2分鐘的題目

竟然可以想了2天

嗯...這似乎不是第一次了

看來我還真的不是普通的腦殘
※ 編輯: cory8249        來自: 111.255.23.104       (06/13 14:27)
推 suhorng:沒聽過"DP"的話...這題不是那麼容易吧
→ angleevil:有聽過,不會做
→ suhorng:通常教DP的話會教這個XD 算很有名的問題之一(?)
推 tropical72:我想看suhorng的原碼和我的想法是否有異,不過我看不到.
→ suhorng:那不是我的部落格...
推 tropical72:嗯, 我連進去了, 確實也是這種解法. XD
→ firejox:分治：http://pastie.org/2060161