由于我忘记了传统的贪心做法，在做一些其他的题目中，遇到了需要求最大子段和问题，于是就有了一下口胡的做法。

记：

$f_{i,1}$ 为前 $i$ 个数的最大子段和

$f_{i,0}$ 为以第 $i$ 个数为结尾的最大子段和

则易得：

$f_{i,0}=\max \{ f_{i-1,0},f_{i-1,1}+a_i,f_{i-1,1},a_i\}$

$f_{i,1}=\max \{f_{i-1,1}+a_i,a_i \}$

$Ans=\max \{f_{n,0},f_{n,1} \}$

初始化: $f_{0,0}=f_{0,1}=-\infty$

这样做好像是对的。

就是说有没有一种可能贪心做法更难想，这个动规更容易想到

其实仔细想想这个和贪心做法其实也没什么区别？