13.最大子数组和

参考链接

53. 最大子数组和 - 力扣（LeetCode）

53. 最大子数组和 - 力扣（LeetCode）- 画手大鹏 题解

个人尝试

class Solution {
    public int maxSubArray(int[] nums) {
        // 特殊情况判断
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        // dp[i]，代表加上nums[i]的最大连续子数组和
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // nums = [-2,1,-3,4,-1,2,1,-5,4]
            // dp      -2,1,-2,4, 3,5,6, 1,5
            // nums = [-2, -1]
            // dp      -2, -1
            dp[i] = Math.max(dp[i -1] + nums[i], nums[i]);
            if (max < dp[i]) max = dp[i];
        }
        return max;
    }
}

参考 「优秀题解」可进一步优化存储空间占用：

class Solution {
    public int maxSubArray(int[] nums) {
        // 特殊情况判断
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        // dp[i]，代表加上nums[i]的最大连续子数组和
        // int[] dp = new int[nums.length];
        // dp[0] = nums[0];
        int sum = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // nums = [-2,1,-3,4,-1,2,1,-5,4]
            // dp      -2,1,-2,4, 3,5,6, 1,5
            // nums = [-2, -1]
            // dp      -2, -1
            // dp[i] = Math.max(dp[i -1] + nums[i], nums[i]);
            // if (max < dp[i]) max = dp[i];
            
            if (sum > 0) sum += nums[i];
            else sum = nums[i];
            
            if (max < sum) max = sum;
        }
        return max;
    }
}

优秀题解

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

作者：画手大鹏
链接：https://leetcode.cn/problems/maximum-subarray/solutions/8975/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。