#14974: 最大區段和


geminibaga (geminibaga)

學校 : 不指定學校
編號 : 54758
來源 : [140.116.239.180]
最後登入時間 :
2024-04-10 12:03:45
b565. 5.採蘑菇攻略問題 -- 102學年度桃竹苗區資訊學科能力競賽 | From: [140.116.250.162] | 發表日期 : 2018-08-24 20:15

 

......, b2, b1, b0, { a1, a2, a3, ....., a7, a8, a9 }, c0, c1, c2, ....

 

如果最大區段和的範圍是落在 { a1~a9 },

則兩邊端點往外延伸部分 ( { b0 }, {b0~b1}, {b0~b2}, ... 與  {c0 }, {c0~c1}, {c0~c2} , ...)  都應該 ≦ 0  

相對的,朝內延伸部分 ( {a0}, {a0~a1}, ... 與 {a9}, {a8~a9} , ...)都應該 ≧ 0

所以碰到加總值小於零時就可以忽略前面的數列了

 

 
ZeroJudge Forum