「最大子数组」最大子数组问题

问题描述

自然语言

给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和.

LeetCode 53. 最大子序和

示例 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}