剑指 Offer 42. 连续子数组的最大和


剑指 Offer 42. 连续子数组的最大和

难度简单 206
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 O(n)。

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

    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) &#123;
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        &#125;
        return res;
    &#125;
// 作者:jyd
// 链接:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/

** 解析**

动态规划是本题的最优解法,以下按照标准流程解题。
动态规划解析:

状态定义: 设动态规划列表 dp ,dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。
为何定义最大和 dp[i] 中必须包含元素 nums[i] :保证 dp[i] 递推到 dp[i+1] 的正确性;如果不包含 nums[i] ,递推时则不满足题目的 连续子数组 要求。
转移方程:
若 dp[i−1]≤0 ,说明 dp[i−1] 对 dp[i] 产生负贡献,即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。
当 dp[i−1]>0 时:执行 dp[i]=dp[i−1]+nums[i] ;
当 dp[i−1]≤0 时:执行 dp[i]=nums[i] ;
初始状态: dp[0]=nums[0],即以 nums[0] 结尾的连续子数组最大和为 nums[0] 。
返回值: 返回 dp 列表中的最大值,代表全局最大值。


易错

     public int maxSubArray(int[] nums) &#123;
        int max=nums[0];//Integer.MIN_VALUE
        int pre=nums[0];//Integer.MIN_VALUE
        for(int i=1;i<nums.length;i++)&#123;
            pre=Math.max(nums[i],pre+nums[i]);//err Math.max(pre,pre+nums[i])
            max=Math.max(pre,max);
        &#125;
        return max;
    &#125;

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
190. 颠倒二进制位 190. 颠倒二进制位
190. 颠倒二进制位难度简单 269颠倒给定的 32 位无符号整数的二进制位。 示例 1:输入: 00000010100101000001111010011100输出: 00111001011110000010100101000000解释
下一篇 
922. 按奇偶排序数组 II 922. 按奇偶排序数组 II
922. 按奇偶排序数组 II难度简单 191给定一个非负整数数组 A, A 中一半整数是奇数,一半整数是偶数。对数组进行排序,以便当 A[i] 为奇数时,i 也是奇数;当 A[i] 为偶数时, i 也是偶数。你可以返回任何满足上述条件的数
2021-03-02 future
  目录