力扣-53.最大子数组和

题目链接

53.最大子数组和

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int res = dp[0];for (int i = 1; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);res = Math.max(res, dp[i]);}return res;}
}

小结：首先想到双指针发现很麻烦，使用动态规划就很简单，dp数组的含义是包含当前数字及以前数字的最大值。