剑指offer-73、连续⼦数组的最⼤和(⼆)

题⽬描述

输⼊⼀个⻓度为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]

思路及解答

暴力枚举

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

public class Solution {public int[] findMaxSubarray(int[] array) {if (array == null || array.length == 0) {return new int[0];}int n = array.length;int maxSum = Integer.MIN_VALUE;int start = 0, end = 0;// 第一重循环：子数组起始位置for (int i = 0; i < n; i++) {// 第二重循环：子数组结束位置for (int j = i; j < n; j++) {int currentSum = 0;// 第三重循环：计算子数组和for (int k = i; k <= j; k++) {currentSum += array[k];}// 更新最大和及位置（优先选择长度更长的）if (currentSum > maxSum || (currentSum == maxSum && (j - i) > (end - start))) {maxSum = currentSum;start = i;end = j;}}}// 构建结果数组int[] result = new int[end - start + 1];System.arraycopy(array, start, result, 0, result.length);return result;}
}

• 时间复杂度：O(n³)，三重循环嵌套
• 空间复杂度：O(1)，除结果外只使用常数空间

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

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

public class Solution {public int[] findMaxSubarray(int[] array) {if (array == null || array.length == 0) {return new int[0];}int n = array.length;int maxSum = Integer.MIN_VALUE;int start = 0, end = 0;// 外层循环：子数组起始位置for (int i = 0; i < n; i++) {int currentSum = 0;// 内层循环：从起始位置向后累加for (int j = i; j < n; j++) {currentSum += array[j]; // 复用之前计算的结果// 更新最大和（优先选择长度更长的）if (currentSum > maxSum || (currentSum == maxSum && (j - i) > (end - start))) {maxSum = currentSum;start = i;end = j;}}}return buildResult(array, start, end);}private int[] buildResult(int[] array, int start, int end) {int[] result = new int[end - start + 1];System.arraycopy(array, start, result, 0, result.length);return result;}
}

• 时间复杂度：O(n²)，减少了一层循环
• 空间复杂度：O(1)，常数级别空间复杂度

分治法（递归思维）

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

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

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

public class Solution {public int[] findMaxSubarray(int[] array) {if (array == null || array.length == 0) {return new int[0];}Result result = findMaxSubarrayHelper(array, 0, array.length - 1);return buildResult(array, result.start, result.end);}private Result findMaxSubarrayHelper(int[] array, int left, int right) {// 基准情况：单个元素if (left == right) {return new Result(left, right, array[left]);}int mid = left + (right - left) / 2;// 递归求解左右两部分Result leftResult = findMaxSubarrayHelper(array, left, mid);Result rightResult = findMaxSubarrayHelper(array, mid + 1, right);Result crossResult = findMaxCrossingSubarray(array, left, mid, right);// 返回三者中的最大值（长度优先）return getMaxResult(leftResult, rightResult, crossResult);}private Result findMaxCrossingSubarray(int[] array, int left, int mid, int right) {// 向左扩展找最大和int leftSum = Integer.MIN_VALUE;int sum = 0;int maxLeft = mid;for (int i = mid; i >= left; i--) {sum += array[i];if (sum > leftSum) {leftSum = sum;maxLeft = i;}}// 向右扩展找最大和int rightSum = Integer.MIN_VALUE;sum = 0;int maxRight = mid + 1;for (int i = mid + 1; i <= right; i++) {sum += array[i];if (sum > rightSum) {rightSum = sum;maxRight = i;}}return new Result(maxLeft, maxRight, leftSum + rightSum);}private Result getMaxResult(Result r1, Result r2, Result r3) {Result maxResult = r1;if (r2.sum > maxResult.sum || (r2.sum == maxResult.sum && (r2.end - r2.start) > (maxResult.end - maxResult.start))) {maxResult = r2;}if (r3.sum > maxResult.sum || (r3.sum == maxResult.sum && (r3.end - r3.start) > (maxResult.end - maxResult.start))) {maxResult = r3;}return maxResult;}private int[] buildResult(int[] array, int start, int end) {int[] result = new int[end - start + 1];System.arraycopy(array, start, result, 0, result.length);return result;}// 辅助类存储子数组结果class Result {int start, end, sum;Result(int s, int e, int sum) {this.start = s;this.end = e;this.sum = sum;}}
}

• 时间复杂度：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])

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

public class Solution85 {public int[] FindGreatestSumOfSubArray(int[] array) {int[] dp = new int[array.length];dp[0] = array[0];int maxsum = dp[0];int left = 0, right = 0;int maxLeft = 0, maxRight = 0;for (int i = 1; i < array.length; i++) {right++;dp[i] = Math.max(dp[i - 1] + array[i], array[i]);if (dp[i - 1] + array[i] < array[i]) {left = right;}// 更新最⼤值以及更新最⼤和的⼦数组的边界if (dp[i] > maxsum || dp[i] == maxsum && (right - left + 1) > (maxRight - maxLeft + 1)) {maxsum = dp[i];maxLeft = left;maxRight = right;}}// 保存结果int[] res = new int[maxRight - maxLeft + 1];for (int i = maxLeft, j = 0; i <= maxRight; i++, j++) {res[j] = array[i];}return res;}
}

• 时间复杂度：O(n)，单次遍历数组
• 空间复杂度：O(1)，只使用常数变量