【LeetCode】53. Maximum Subarray

题目描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

解题思路

动态规划。 对于从0到i，要使得当前的状态取值最大，那么，对于前一个状态的最大值，考虑如下两种情况：

也就是说，有如下的状态转移方程：

AC代码