題目連結

https://zerojudge.tw/ShowProblem?problemid=a540

參考文章

X

本題要點

第一想法寫出雙重迴圈逐步檢查,顯然行不通,TLE 3sec(錯一)

後來優化後改用一個迴圈完成,cur 紀錄當前 贏/輸 多少

加上下一局金額時,如果該局金額贏錢比之前到現在贏得還多

就更新 cur 將該次(最佳情況)當作第一局

並且更新 maxnum 紀錄最大連續局可以贏多少錢

如下方範例

-99 10 -9 10 -5 4

當 i = 1 時 cur = -99,此時 nums[i] > cur + nums[i]

將 cur 更新為 cur = 10,因為前面連續局數贏的錢比現在該局贏得金額還少

所以更新 cur 並且將此局當作連續局的第一局(有點繞口令)

不仿跟著數列跑一次,就可以理解原因了

解二則是用DP來解,跟解一的方式類似,變成將每次的值紀錄在 DP 當中

最後,一次找出max(DP),不用每次更新