题目链接

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [0]
输出：0

示例 4：

输入：nums = [-1]
输出：-1

示例 5：

输入：nums = [-100000]
输出：-100000

提示：

  • 1 <= nums.length <= 3 * 104
  • -105 <= nums[i] <= 105

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

思路：

三种情况：

  • 全部为负数
    • 返回最大的正数
  • 全部为正数
    • 全部累加
  • 有正有负
    • 找到第一个正数 => 第一个必定是正数
    • 继续遍历，如果连续遇到正数，相加，如果负数保持不变，直到遇到下一个正数
    • 继续遍历，然后重复第二步，第二步完成后得到新的子串结果，比较两个子串结果，取最大，重复 2 3步，直到遍历完成

      其实这里就有贪心算法的思想了：

      贪心贪的是哪里呢？ 如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方

      局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

      全局最优：选取最大“连续和

      局部最优的情况下，并记录最大的“连续和”，可以推出全局最优

代码实现

  1. public int maxSubArray(int[] nums) {
  2.     // 结果最大值
  3.     int res = nums[0];
  5.     // sum相当于一个测试变量，测试下一个是否比原来的大值还要大
  6.     // 也是一个临时存储变量
  7.     int sum = 0;
  9.     for (int num : nums) {
  10.         if (sum > 0) {
  11.             // 如果累加和大于零，吃掉下一个数
  12.             sum += num;
  13.         }
  14.         else {
  15.             // 如果当前累加和小于0，重新赋值
  16.             sum = num;
  17.         }
  18.         // 因为对于负数都是每次重新赋值，并且都取最大值保存
  19.         // 所以在找到第一个正数过程中，可以找到最大的负数
  20.         // 同时这里也是更新 res，如果用指针看待，就是更新头尾指针的地方
  21.         res = Math.max(res, sum);
  22.     }
  23.     return res;
  24. }

答案

动态规划

image.png
这个没太看懂

代码实现

  1. public int maxSubArray(int[] nums) {
  2.     // pre来维护对于当前 f(i) 的 f(i−1) 的值是多少
  3.     int pre = 0, maxAns = nums[0];
  4.     for (int x : nums) {
  5.         // 判断f(i-1)是否要加到当前数上
  6.         pre = Math.max(pre + x, x); 
  7.         // 获取最大值
  8.         maxAns = Math.max(maxAns, pre);
  9.     }
  10.     return maxAns;
  11. }

分治算法

首先说明一点, 对于这道题而言, 分治法是不如上面的两种算法的, 在时间复杂度相同的情况下, 分治法还具有更高的空间复杂度. 分治法的意义如下图所示, 这里讲解它, 主要是为了让大家先了解一下 线段树 这种数据结构, 它还是有很广泛的应用场景的, 毕竟我们刷算法也是学习的过程, 早晚也都会接触到它的. !

分治法的思想
大家直接看官方题解的思想可能会一头雾水, 根本不知道这些要维护的变量是怎么来的, 我找到了另外一篇文章详细介绍了整个思想的流程, 说明了变量是如何一步一步获得的, 讲解的还是挺清楚的, 如果还是感觉不太懂, 可以看看我录制的配套视频, 根据图片更详细的说明了整个推导过程. !
理解了推导过程后, 再来看官方的题解就比较清晰了, 也能明白每个变量的由来了. 下面是我整理的官方题解的思路: !

  1. // 分治法: 线段树
  2. class Solution {
  3.     public int maxSubAray(int[] nums) {
  4.         if (nums == null || nums.length <= 0)// 输入校验
  5.             return 0;
  6.         int len = nums.length;// 获取输入长度
  7.         return getInfo(nums, 0, len - 1).mSum;
  8.     }
  10.     class wtevTree { //线段树
  11.         int lSum;// 以左区间为端点的最大子段和
  12.         int rSum;// 以右区间为端点的最大子段和
  13.         int iSum;// 区间所有数的和
  14.         int mSum;// 该区间的最大子段和
  15.         wtevTree(int l, int r, int i, int m) { // 构造函数
  16.             lSum = l;
  17.             rSum = r;
  18.             iSum = i;
  19.             mSum = m;
  20.         }
  21.     }
  23.     // 通过既有的属性,计算上一层的属性,一步步往上返回,获得线段树
  24.     wtevTree pushUp(wtevTree leftT, wtevTree rightT) {
  25.         // 新子段的lSum等于左区间的lSum或者左区间的 区间和 加上右区间的lSum
  26.         int l = Math.max(leftT.lSum, leftT.iSum + rightT.lSum);
  27.         // 新子段的rSum等于右区间的rSum或者右区间的 区间和 加上左区间的rSum
  28.         int r = Math.max(leftT.rSum + rightT.iSum, rightT.rSum);
  29.         // 新子段的区间和等于左右区间的区间和之和
  30.         int i = leftT.iSum + rightT.iSum;
  31.         // 新子段的最大子段和,其子段有可能穿过左右区间,或左区间,或右区间
  32.         int m = Math.max(leftT.rSum + rightT.lSum, Math.max(leftT.mSum, rightT.mSum));
  33.         return new wtevTree(l, r, i, m);
  34.     }
  36.     // 递归建立和获得输入区间所有子段的结构
  37.     wtevTree getInfo(int[] nums, int left, int right) {
  38.         if (left == right) // 若区间长度为1,其四个子段均为其值
  39.             return new wtevTree(nums[left], nums[left], nums[left], nums[left]);
  40.         int mid = (left + right) >> 1;// 获得中间点mid,右移一位相当于除以2,运算更快
  41.         wtevTree leftT = getInfo(nums, left, mid);
  42.         wtevTree rightT = getInfo(nums, mid + 1, right);//mid+1,左右区间没有交集。
  43.         return pushUp(leftT, rightT);//递归结束后,做最后一次合并
  44.     }
  45. }