LeetCode[53].最大子数组和

Note
(1) dp[n]的含义是以下标 n 为结尾的 前 n 个数中的最大子数组和(注意必须是以 n 为结尾的,而不是前 n 个数中的最大子数组和)
(2) 最开始出错把ans 初始化为Integer.MIN_VALUE 这种情况在数组中只有一个数时，答案会出错正确做法应该初始化为 dp[0]
(3) 注意递推公式应该为dp[i] = Math.max(nums[i],dp[i-1]+nums[i]); 而不是dp[i] = Math.max(dp[i],dp[i-1]+nums[i]); 因为 dp[n] 的初始值都为 0 ,若数组中都是负数,就会得到错误答案0 应该直接和当前下标所在的值进行比较并更新 dp 数组

代码：

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

Note
(1) dp[n]的含义是以下标 n 为结尾的 前 n 个数中的最大子数组和(注意必须是以 n 为结尾的,而不是前 n 个数中的最大子数组和)
(2) 最开始出错把ans 初始化为Integer.MIN_VALUE 这种情况在数组中只有一个数时，答案会出错正确做法应该初始化为 dp[0]
(3) 注意递推公式应该为dp[i] = Math.max(nums[i],dp[i-1]+nums[i]); 而不是dp[i] = Math.max(dp[i],dp[i-1]+nums[i]); 因为 dp[n] 的初始值都为 0 ,若数组中都是负数,就会得到错误答案0 应该直接和当前下标所在的值进行比较并更新 dp 数组

代码：

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