南宁企业如何建网站,动漫制作专业可以专升本吗,中国农技推广网,义乌多语言网站建设53.最大子数组和 1、题目2、题目分析3、解题步骤4、复杂度最优解代码示例5、抽象与扩展 1、题目
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组 是数组中的一个连… 53.最大子数组和 1、题目2、题目分析3、解题步骤4、复杂度最优解代码示例5、抽象与扩展 1、题目
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。
示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6 。
示例 2 输入nums [1] 输出1
示例 3 输入nums [5,4,-1,7,8] 输出23
提示 1 nums.length 105 -104 nums[i] 104
进阶如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。
2、题目分析
求连续子数组的最大和意味着对数组切分成多段此时有 2 个要点
如何切分什么情况下子数组还能接着往后连续下去 求连续子数组的最大和当子数组遇到新值时 如果加该值子数组的和大于该值则让子数组继续往下遍历的效果更佳 如果加该值子数组的和小于该值则不如让子数组在这做分割然后下一个子数组从该新值开始。对切分后的每一段数据做什么操作 进行值的累加并对比记录下各段子数组和的最大值。
3、解题步骤
初始化 2 个值 a. 每段子数组的和0 b. 各段子数组和的最大值max数组首个元素不能初始化为0避免数组各段子数组和的最大值小于0的情况遍历数组并做 2 步 a. sum max(上个子数组 当前新值当前新值)。即判断上个子数组是否还往下扩展还是在此截止。 b. max max(sum, max)。即max对比记录下各段子数组和的最大值。
4、复杂度最优解代码示例 public int maxSubArray(int[] nums) {int sum 0;// 踩坑这里不能初始化为 0。如当数组只有1个元素且为负数时max不会被替换为负数。int max nums[0];for (int i 0; i nums.length; i) {// a. sum max(上个子数组 当前新值当前新值)。即判断上个子数组是否还往下扩展还是在此截止。sum Math.max(sum nums[i], nums[i]);// b. max max(sum, max)。即max对比记录下各段子数组和的最大值。max Math.max(sum, max);}return max;}5、抽象与扩展
求连续子数组/子串的和值等问题核心就是找到子数组/子串是否往下扩展的条件。
如本题中 子数组要往下扩展的条件就是子数组的和 新值 新值则子数组接着往下扩展。 否则新值 另起一个子数组。
