[每日一题] 第十五题:连续子数组的最大和

题目描述

输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

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

提示:

  • 1 <= arr.length <= 10^5
  • -100 <= arr[i] <= 100

题解

方法一:动态规划

解题思路:

常见解法 时间复杂度 空间复杂度
暴力搜索 O(N^2) O(1)
分治思想 O(NlogN) O(logN)
动态规划 O(N) O(1)

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

动态规划解析:

  • 状态定义: 设动态规划列表 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 列表中的最大值,代表全局最大值。

[每日一题] 第十五题:连续子数组的最大和

空间复杂度降低:

  • 由于 dp[i] 只与 dp[i-1] 和 nums[i] 有关系,因此可以将原数组 nums 用作 dp 列表,即直接在 nums 上修改即可。
  • 由于省去 dp 列表使用的额外空间,因此空间复杂度从 O(N) 降至 O(1)。

复杂度分析

  • 时间复杂度: 线性遍历数组 nums 即可获得结果,使用 O(N) 时间。
  • 空间复杂度: 使用常数大小的额外空间。

代码

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

个人理解

  1. 确定动态规划解题思路: 没有经验的话把这道题想成用动态规划去解决还是很难的,这题能用动态规划去实现,有一个很重要的一点,确定状态,想到用 dp[i] 来表示到 nums[i] 的最大值这个很重要。
  2. 状态转移方程: 因为我们要进行空间优化,所以我们省去了 dp 数组,而是将原来的 nums 数组当成 dp 数组,所以我们应该想到状态转移方程为 nums[i] += (nums[i-1] > 0) ? nums[i-1] : 0;
  3. 大小比较: 这个我是第一次使用,Math.max() 方法,里面要传入两个值,所以每次 for 循环都要比较。

题解来源

作者:jyd
链接:leetcode-cn.com/problems/lian-xu-z...
来源:力扣(LeetCode)

来源

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/lian-xu-z...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!