剑指offer-30、连续⼦数组的最⼤和

题⽬描述

输⼊⼀个整型数组，数组⾥有正数也有负数。数组中的⼀个或连续多个整数组成⼀个⼦数组。求所有⼦数组的和的最⼤值。要求时间复杂度为 O(n) .
示例1
输⼊：[1,-2,3,10,-4,7,2,-5]
返回值：18
输⼊的数组为 {1,-2,3,10,-4,7,2,-5} ，和最⼤的⼦数组为 {3,10,-4,7,2} ，因此输出为该⼦数组的和 18 。
思路及解答

暴⼒破解

通过两层循环枚举所有可能的子数组起点和终点，计算每个子数组的和并记录最大值。

1. public class Solution {
2.     public int maxSubArray(int[] nums) {
3.         int n = nums.length;
4.         int maxSum = Integer.MIN_VALUE; // 初始化为最小整数，以处理全负数数组
6.         for (int i = 0; i < n; i++) {
7.             int currentSum = 0; // 记录从i开始到j的子数组和
8.             for (int j = i; j < n; j++) {
9.                 currentSum += nums[j]; // 累加当前元素
10.                 if (currentSum > maxSum) {
11.                     maxSum = currentSum; // 更新全局最大和
12.                 }
13.             }
14.         }
15.         return maxSum;
16.     }
17. }

复制代码

• 时间复杂度​：O(n²)，因为有两层嵌套循环。
  
• ​空间复杂度​：O(1)，只使用了常数级别的额外空间。
  

分治法

分治法将数组分成左右两半，分别递归求解左右半边的最大子数组和，再计算跨越中点的最大子数组和，最后合并结果。

1. public class Solution {
2.     public int maxSubArray(int[] nums) {
3.         return divideAndConquer(nums, 0, nums.length - 1);
4.     }
6.     private int divideAndConquer(int[] nums, int left, int right) {
7.         if (left == right) {
8.             return nums[left]; // 递归基：只有一个元素
9.         }
11.         int mid = left + (right - left) / 2;
12.         int leftMax = divideAndConquer(nums, left, mid); // 左半部分的最大子数组和
13.         int rightMax = divideAndConquer(nums, mid + 1, right); // 右半部分的最大子数组和
14.         int crossMax = maxCrossingSum(nums, left, mid, right); // 跨越中点的最大子数组和
16.         return Math.max(Math.max(leftMax, rightMax), crossMax); // 返回三者中的最大值
17.     }
19.     private int maxCrossingSum(int[] nums, int left, int mid, int right) {
20.         int leftSum = Integer.MIN_VALUE;
21.         int sum = 0;
22.         for (int i = mid; i >= left; i--) { // 从中点向左扫描
23.             sum += nums[i];
24.             if (sum > leftSum) {
25.                 leftSum = sum;
26.             }
27.         }
29.         int rightSum = Integer.MIN_VALUE;
30.         sum = 0;
31.         for (int i = mid + 1; i <= right; i++) { // 从中点向右扫描
32.             sum += nums[i];
33.             if (sum > rightSum) {
34.                 rightSum = sum;
35.             }
36.         }
38.         return leftSum + rightSum; // 合并左右两部分的和
39.     }
40. }

复制代码

• ​时间复杂度​：O(n log n)，由递归树深度（log n）和每层合并操作（n）决定。
  
• ​空间复杂度​：O(log n)，递归调用栈的深度。
  

动态规划

⾸先我们定义这个问题：
dp 表示下标以i结尾的连续⼦数组的最⼤和，假设数组⼤⼩为 n ,那么最终求解的就是 dp[n-1] 。
下标以 i 结尾的连续⼦数组的最⼤和，怎么求呢？
要想求 dp ,那我们现在假设⼀下，假设下标以i-1 结尾的连续⼦数组的最⼤和为 dp[i-1] ,数组第 i 个元素是 nums ，那么当前的连续⼦数组的最⼤和，要么是前⾯的加上当前的元素： dp[i-1]+nums ，要么是舍弃掉之前的 dp[i-1]（这个很可能是负数） ，取现在的 nums ;
因此，状态转移⽅程为：dp = max{dp[i-1]+nums  , nums}
但是，值得注意的是， Max{dp[i-1]+nums,nums} 求得的仅仅是以 i 下标结尾的⼦数组的最⼤和，之前计算的连续⼦数组最⼤和需要保存起来，不断的和当前计算的最⼤和⽐较，取最⼤值。

1. public int FindGreatestSumOfSubArray(int[] array) {
2.         int res = array[0]; //记录当前所有⼦数组的和的最⼤值
3.         int[] dp = new int[array.length];
4.         dp[0] = array[0];
5.        
6.         for (int i = 1; i < array.length; i++) {
7.                 dp[i] = Math.max(dp[i-1] + array[i], array[i]);
8.                 res = Math.max(max, res);
9.         }
10.        
11.         return res;
12. }

复制代码

• 时间复杂度：O(n)
  
• 空间复杂度：O(n)
  

这里只用到了dp和dp[i-1]，显然还可以再优化。即

1. public int FindGreatestSumOfSubArray(int[] array) {
2.         int res = array[0]; //记录当前所有⼦数组的和的最⼤值
3.         int max = array[0]; //包含array[i]的连续数组最⼤值
4.        
5.         for (int i = 1; i < array.length; i++) {
6.                 max = Math.max(max + array[i], array[i]);
7.                 res = Math.max(max, res);
8.         }
9.        
10.         return res;
11. }

复制代码

• 时间复杂度：O(n)
  
• 空间复杂度：O(1)，只使用了两个变量。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！