UVa10684 The jackpot

經典的題目(?)

基礎題

連結：UVa10684 The jackpot

題目：

求一序列中總和最大的連續子序列之值

如12 -4 -10 4 9的答案為13

做法：

用一個SUM來累加a[i]，並不斷更新ans

GREEDY

若sum < 0

則代表前面這段無益，sum = 0

反之則繼續加，

如果後來累加的更大，屆時就會更新到ans

如果變小，則ans也不會被更新

可以解釋ans能維護我們要的答案

個人覺得這個方法比DP直觀

code: