题目来自剑指 offer第 42题
动态规划
思路
- 定义状态: dp[i] 为数组 [0…i]中的最大和, 一定包含dp[i]
注意是连续子数组, 所以必须包含最后一个元素, 否则就断了
-
定义输出: dp[]中最大的值
-
状态转移方程:
dp[i] = dp[i - 1] >= 0 ? dp[i - 1] + nums[i] : nums[i]
因为一定包含 nums[i], 所以如果 dp[i-1] >=0, 求最大值, 就加上
代码
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length + 1];
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < nums.length; i++) {
if (dp[i - 1] >= 0) dp[i] = dp[i - 1] + nums[i];
else dp[i] = nums[i];
res = Math.max(res, dp[i]);
}
return res;
}