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

题⽬描述输⼊⼀个⻓度为n 的整型数组array 数组中的⼀个或连续多个整数组成⼀个⼦数组找到⼀个具有最⼤和的连续⼦数组。⼦数组是连续的⽐如[1,3,5,7,9] 的⼦数组有[1,3] [3,5,7] 等等但是[1,3,7] 不是⼦数组如果存在多个最⼤和的连续⼦数组那么返回其中⻓度最⻓的该题数据保证这个最⻓的只存在⼀个该题定义的⼦数组的最⼩⻓度为1 不存在为空的⼦数组即不存在[]是某个数组的⼦数组返回的数组不计⼊空间复杂度计算示例 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]思路及解答暴力枚举通过三重循环枚举所有可能的子数组使用三重循环枚举所有可能的子数组起始和结束位置计算每个子数组的和javapublic 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)除结果外只使用常数空间优化枚举法前缀和思想在暴力法基础上优化利用前缀和在计算子数组和时复用之前的结果减少一层循环javapublic 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)常数级别空间复杂度分治法递归思维采用分治思想将问题分解为更小的子问题将问题分解为左半部分、右半部分和跨越中间的三部分即递归求解左右子数组合并时处理跨越中间的情况javapublic 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 个元素突然加上⼀个元素变成 n1 个元素对连续⼦数组的最⼤和有什么影响呢我们只需要知道以每⼀个元素结尾的最⼤连续⼦数组再维护⼀个最⼤的值即可。假设数组为num[] ⽤ dp[i] 表示以下标 i 为终点的最⼤连续⼦数组和遍历每⼀个新的元素nums[i1] 以 num[i1] 为连续⼦数组的情况只有两种dp[i] num[i1]只有num[i1]所以以nums[n] 结尾的最⼤连续⼦数组和为 dp[i] max( dp[i-1] num[i], num[i])在计算的过程中需要维护⼀个最⼤的值并且把该连续⼦数组的左边界以及右边界维护好最后根据维护的区间返回。javapublic 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)只使用常数变量