剑指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]
思路及解答

暴力枚举

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

1. public class Solution {
2.     public int[] findMaxSubarray(int[] array) {
3.         if (array == null || array.length == 0) {
4.             return new int[0];
5.         }
6.         
7.         int n = array.length;
8.         int maxSum = Integer.MIN_VALUE;
9.         int start = 0, end = 0;
10.         
11.         // 第一重循环：子数组起始位置
12.         for (int i = 0; i < n; i++) {
13.             // 第二重循环：子数组结束位置
14.             for (int j = i; j < n; j++) {
15.                 int currentSum = 0;
16.                 // 第三重循环：计算子数组和
17.                 for (int k = i; k <= j; k++) {
18.                     currentSum += array[k];
19.                 }
20.                
21.                 // 更新最大和及位置（优先选择长度更长的）
22.                 if (currentSum > maxSum || (currentSum == maxSum && (j - i) > (end - start))) {
23.                     maxSum = currentSum;
24.                     start = i;
25.                     end = j;
26.                 }
27.             }
28.         }
29.         
30.         // 构建结果数组
31.         int[] result = new int[end - start + 1];
32.         System.arraycopy(array, start, result, 0, result.length);
33.         return result;
34.     }
35. }

复制代码

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

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

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

1. public class Solution {
2.     public int[] findMaxSubarray(int[] array) {
3.         if (array == null || array.length == 0) {
4.             return new int[0];
5.         }
6.         
7.         int n = array.length;
8.         int maxSum = Integer.MIN_VALUE;
9.         int start = 0, end = 0;
10.         
11.         // 外层循环：子数组起始位置
12.         for (int i = 0; i < n; i++) {
13.             int currentSum = 0;
14.             // 内层循环：从起始位置向后累加
15.             for (int j = i; j < n; j++) {
16.                 currentSum += array[j]; // 复用之前计算的结果
17.                
18.                 // 更新最大和（优先选择长度更长的）
19.                 if (currentSum > maxSum || (currentSum == maxSum && (j - i) > (end - start))) {
20.                     maxSum = currentSum;
21.                     start = i;
22.                     end = j;
23.                 }
24.             }
25.         }
26.         
27.         return buildResult(array, start, end);
28.     }
29.    
30.     private int[] buildResult(int[] array, int start, int end) {
31.         int[] result = new int[end - start + 1];
32.         System.arraycopy(array, start, result, 0, result.length);
33.         return result;
34.     }
35. }

复制代码

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

分治法（递归思维）

采用分治思想，将问题分解为更小的子问题
将问题分解为左半部分、右半部分和跨越中间的三部分
即递归求解左右子数组，合并时处理跨越中间的情况

1. public class Solution {
2.     public int[] findMaxSubarray(int[] array) {
3.         if (array == null || array.length == 0) {
4.             return new int[0];
5.         }
6.         Result result = findMaxSubarrayHelper(array, 0, array.length - 1);
7.         return buildResult(array, result.start, result.end);
8.     }
9.    
10.     private Result findMaxSubarrayHelper(int[] array, int left, int right) {
11.         // 基准情况：单个元素
12.         if (left == right) {
13.             return new Result(left, right, array[left]);
14.         }
15.         
16.         int mid = left + (right - left) / 2;
17.         
18.         // 递归求解左右两部分
19.         Result leftResult = findMaxSubarrayHelper(array, left, mid);
20.         Result rightResult = findMaxSubarrayHelper(array, mid + 1, right);
21.         Result crossResult = findMaxCrossingSubarray(array, left, mid, right);
22.         
23.         // 返回三者中的最大值（长度优先）
24.         return getMaxResult(leftResult, rightResult, crossResult);
25.     }
26.    
27.     private Result findMaxCrossingSubarray(int[] array, int left, int mid, int right) {
28.         // 向左扩展找最大和
29.         int leftSum = Integer.MIN_VALUE;
30.         int sum = 0;
31.         int maxLeft = mid;
32.         for (int i = mid; i >= left; i--) {
33.             sum += array[i];
34.             if (sum > leftSum) {
35.                 leftSum = sum;
36.                 maxLeft = i;
37.             }
38.         }
39.         
40.         // 向右扩展找最大和
41.         int rightSum = Integer.MIN_VALUE;
42.         sum = 0;
43.         int maxRight = mid + 1;
44.         for (int i = mid + 1; i <= right; i++) {
45.             sum += array[i];
46.             if (sum > rightSum) {
47.                 rightSum = sum;
48.                 maxRight = i;
49.             }
50.         }
51.         
52.         return new Result(maxLeft, maxRight, leftSum + rightSum);
53.     }
54.    
55.     private Result getMaxResult(Result r1, Result r2, Result r3) {
56.         Result maxResult = r1;
57.         if (r2.sum > maxResult.sum || (r2.sum == maxResult.sum && (r2.end - r2.start) > (maxResult.end - maxResult.start))) {
58.             maxResult = r2;
59.         }
60.         if (r3.sum > maxResult.sum || (r3.sum == maxResult.sum && (r3.end - r3.start) > (maxResult.end - maxResult.start))) {
61.             maxResult = r3;
62.         }
63.         return maxResult;
64.     }
65.    
66.     private int[] buildResult(int[] array, int start, int end) {
67.         int[] result = new int[end - start + 1];
68.         System.arraycopy(array, start, result, 0, result.length);
69.         return result;
70.     }
71.    
72.     // 辅助类存储子数组结果
73.     class Result {
74.         int start, end, sum;
75.         Result(int s, int e, int sum) {
76.             this.start = s;
77.             this.end = e;
78.             this.sum = sum;
79.         }
80.     }
81. }

复制代码

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

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

遍历数组，维护当前子数组和，根据规则重置或扩展当前子数组
假设现在有 n 个元素，突然加上⼀个元素，变成 n+1 个元素，对连续⼦数组的最⼤和有什么影响呢？

我们只需要知道以每⼀个元素结尾的最⼤连续⼦数组，再维护⼀个最⼤的值即可。
假设数组为num[] ，⽤ dp 表示以下标 i 为终点的最⼤连续⼦数组和，遍历每⼀个新的元素nums[i+1] ，以 num[i+1] 为连续⼦数组的情况只有两种：

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

所以以nums[n] 结尾的最⼤连续⼦数组和为： dp = max( dp[i-1] + num,  num)
在计算的过程中，需要维护⼀个最⼤的值，并且把该连续⼦数组的左边界以及右边界维护好，最后根据维护的区间返回。
[code]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 = Math.max(dp[i - 1] + array, array);            if (dp[i - 1] + array < array) {                left = right;            }            // 更新最⼤值以及更新最⼤和的⼦数组的边界            if (dp > maxsum || dp == maxsum && (right - left + 1) > (maxRight - maxLeft + 1)) {                maxsum = dp;                maxLeft = left;                maxRight = right;            }        }        // 保存结果        int[] res = new int[maxRight - maxLeft + 1];        for (int i = maxLeft, j = 0; i

谢谢分享，辛苦了

感谢分享，学习下。

懂技术并乐意极积无私分享的人越来越少。珍惜

收藏一下   不知道什么时候能用到

感谢分享

过来提前占个楼

这个好，看起来很实用

不错，里面软件多更新就更好了

分享、互助 让互联网精神温暖你我

用心讨论，共获提升！