题⽬描述

输⼊⼀个⻓度为n 的整型数组array，数组中的⼀个或连续多个整数组成⼀个⼦数组，找到⼀个具有 最⼤和的连续⼦数组。

  1. ⼦数组是连续的，⽐如[1,3,5,7,9] 的⼦数组有[1,3]， [3,5,7] 等等，但是[1,3,7] 不是⼦数组

  2. 如果存在多个最⼤和的连续⼦数组，那么返回其中⻓度最⻓的，该题数据保证这个最⻓的只存在⼀个

  3. 该题定义的⼦数组的最⼩⻓度为1，不存在为空的⼦数组，即不存在[]是某个数组的⼦数组

  4. 返回的数组不计⼊空间复杂度计算

示例 1 输⼊：[1,-2,3,10,-4,7,2,-5] 返回值：[3,10,-4,7,2] 说明：经分析可知，输⼊数组的⼦数组[3,10,-4,7,2]可以求得最⼤和为18，故返回[3,10,-4,7,2]

示例 2 输⼊：[1] 返回值：[1]

思路及解答

暴力枚举

通过三重循环枚举所有可能的子数组，使用三重循环枚举所有可能的子数组起始和结束位置，计算每个子数组的和

  • 时间复杂度：O(n³)，三重循环嵌套

  • 空间复杂度：O(1)，除结果外只使用常数空间

优化枚举法（前缀和思想）

在暴力法基础上优化，利用前缀和在计算子数组和时复用之前的结果，减少一层循环

  • 时间复杂度：O(n²)，减少了一层循环

  • 空间复杂度：O(1)，常数级别空间复杂度

分治法

采用分治思想，将问题分解为更小的子问题

将问题分解为左半部分、右半部分和跨越中间的三部分

即递归求解左右子数组，合并时处理跨越中间的情况

  • 时间复杂度：O(n log n)，递归深度为log n，每层处理时间为O(n)

  • 空间复杂度：O(log n)，递归调用栈的深度

动态规划-Kadane算法（最优解）

遍历数组，维护当前子数组和，根据规则重置或扩展当前子数组

假设现在有 n 个元素，突然加上⼀个元素，变成 n+1 个元素，对连续⼦数组的最⼤和有什么影响呢？ 我们只需要知道以每⼀个元素结尾的最⼤连续⼦数组，再维护⼀个最⼤的值即可。

假设数组为num[]，⽤ dp[i] 表示以下标 i 为终点的最⼤连续⼦数组和，遍历每⼀个新的元素nums[i+1]，以 num[i+1] 为连续⼦数组的情况只有两种：

  • dp[i] + num[i+1]

  • 只有num[i+1]

所以以nums[n] 结尾的最⼤连续⼦数组和为： dp[i] = max( dp[i-1] + num[i], num[i])

在计算的过程中，需要维护⼀个最⼤的值，并且把该连续⼦数组的左边界以及右边界维护好，最后根据维护的区间返回。

  • 时间复杂度：O(n)，单次遍历数组

  • 空间复杂度：O(1)，只使用常数变量