leetcode题目51. 最大子数组和

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

示例

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

代码

  // 方法一： 若当前和小于0，则抛弃当前元素之前的数列。
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        int maxResult = Integer.MIN_VALUE;
        int tempResult = 0;
        for (int i = 0; i < nums.length; i++) {
            if (tempResult >= 0) {
                // 如果结果大于0，则继续相加
                tempResult = tempResult + nums[i];
            } else {
                // 如果结果小于0，则抛弃之前的和
                tempResult = nums[i];
            }
            if (maxResult < tempResult) {
                // 保存最大的和
                maxResult = tempResult;
            }
        }
        return maxResult;
    }


    // 解法二：动态规划
    // 状态转移方程： f(i) = max{f(i - 1) + nums[i], nums[i]}
    // f(i) 指的是nums数组中以nums[i]为结尾的"连续子数组的最大和"
    public int maxSubArrayV2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        int maxResult = nums[0];
        int tempResult = nums[0];
        for (int i = 1; i < nums.length; i++) {
            tempResult = Math.max(nums[i], tempResult + nums[i]);
            maxResult = Math.max(tempResult, maxResult);
        }
        return maxResult;
    }