无疑，dp是正解。

不过本蒟蒻似乎想到了分治的算法......?

可以把这个数组分为$A_{low...mid}$与$A_{mid+1...high}$，然后对着两部分进行递归。

有一种特殊情况是这个最大子数组跨越了中点$mid$，不过这个问题不难解决。

时间复杂度似乎是（我太蒻了不敢确定）$\Theta(n \lg n)$的。