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