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),不用每次更新