「最大子数组」最大子数组问题
问题描述
自然语言
给定一个整数数组
nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和.
示例 1
1输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
2输出：6
3解释：连续子数组 [4,-1,2,1] 的和最大，为 6 .
示例 2
1输入：nums = [1]
2输出：1
示例 3
1输入：nums = [0]
2输出：0
示例 4
1输入：nums = [-1]
2输出：-1
示例 5
1输入：nums = [-100000]
2输出：-100000
解题思路
暴力解法
穷举出子数组的所有可能性，依次计算它们的和，并求得最大值.不难得出，子数组的个数为 $C_n^2=\frac{n(n-1)}{2}=\Theta(n^2)$，计算每个子数组的和可以在线性时间内完成，因此整个算法的复杂度为 $\Theta(n^3)$
设输入为 nums[0..high]
算法简述
1max = -∞
2for i=0 upto high
3 for j=i+1 upto high
4 count = 0
5 for k=i upto j
6 count += nums[k]
7 if count > max
8 max = count
9return max
不过我们可以通过记录从前的值，将计算子数组的和这一操作在 $O(1)$ 时间中完成.
算法简述
1max = -∞
2for i=0 upto high
3 count = 0
4 for j=i upto high
5 count += num[j]
6 if count > max
7 max = count
8return max
则此时算法的复杂度将降低到 $\Theta(n^2)$.
附录
暴力解法代码实现
1public int maxSubArray(int[] nums) {
2 int max = Integer.MIN_VALUE;
3 for (int i = 0; i < nums.length; i++) {
4 int count = 0;
5 for (int j = i; j < nums.length; j++) {
6 count += nums[j];
7 if (count > max) {
8 max = count;
9 }
10 }
11 }
12 return max;
13}