最大子数组和

Posted on Edited on In

题目描述
给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入格式
输入共 2 行：

  • 第一行包含一个整数 n，表示数组的长度。
  • 第二行包含 n 个整数，表示数组 nums 的元素。

输出格式
输出共 1 行，包含一个整数，表示最大子数组和。

数据范围
1 ≤ n ≤ 3 * 10^4
-10^5 ≤ nums[i] ≤ 10^5

输入样例1：

1
2
9
-2 1 -3 4 -1 2 1 -5 4

输出样例1：

1
6

输入样例2：

1
2
1
1

输出样例2：

1
1

输入样例3：

1
2
5
5 4 -1 7 8

输出样例3：

1
23

注意事项

  • 可以使用暴力枚举法，但时间复杂度为O(n²)，对于大规模数据可能会超时。
  • 动态规划方法的时间复杂度为O(n)，空间复杂度为O(n)。
  • 可以进一步优化空间复杂度到O(1)。
  • 还可以使用分治算法来解决这个问题。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 方法一：暴力枚举法（不推荐用于大规模数据）
int maxSubArrayBruteForce(vector<int>& nums)
{
    int n = nums.size();
    int maxSum = INT_MIN;
    
    for (int i = 0; i < n; i++)
    {
        int currentSum = 0;
        for (int j = i; j < n; j++)
        {
            currentSum += nums[j];
            maxSum = max(maxSum, currentSum);
        }
    }
    
    return maxSum;
}

// 方法二：动态规划法
int maxSubArrayDP(vector<int>& nums)
{
    int n = nums.size();
    vector<int> dp(n); // dp[i] 表示以nums[i]结尾的最大子数组和
    dp[0] = nums[0];
    int maxSum = dp[0];
    
    for (int i = 1; i < n; i++)
    {
        // 要么将nums[i]加入前面的子数组，要么以nums[i]开始一个新的子数组
        dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        maxSum = max(maxSum, dp[i]);
    }
    
    return maxSum;
}

// 方法三：动态规划法（空间优化版）
int maxSubArrayDPOptimized(vector<int>& nums)
{
    int n = nums.size();
    int currentSum = nums[0];
    int maxSum = nums[0];
    
    for (int i = 1; i < n; i++)
    {
        // 要么将nums[i]加入前面的子数组，要么以nums[i]开始一个新的子数组
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

int main()
{
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    
    // 使用空间优化的动态规划法求解
    int result = maxSubArrayDPOptimized(nums);
    
    // 如果要使用普通动态规划法，可以取消下面这行的注释，并注释掉上面这行
    // int result = maxSubArrayDP(nums);
    
    // 如果要使用暴力枚举法，可以取消下面这行的注释，并注释掉上面这行
    // int result = maxSubArrayBruteForce(nums);
    
    cout << result << endl;
    
    return 0;
}

时间复杂度

  • 暴力枚举法时间复杂度：O(n²)，其中 n 是数组的长度。
  • 动态规划法时间复杂度：O(n)，其中 n 是数组的长度。
  • 空间复杂度：O(1)（空间优化的动态规划法）或 O(n)（普通动态规划法）。

代码解释

  • 最大子数组和问题是一个经典的动态规划问题。
  • 暴力枚举法的思想是枚举所有可能的子数组，并计算它们的和，找出最大的那个。这种方法的时间复杂度较高，但实现简单。
  • 动态规划法的思想是使用dp[i]表示以nums[i]结尾的最大子数组和。对于每个元素nums[i]，我们有两个选择：要么将它加入前面的子数组，要么以它开始一个新的子数组。因此，dp[i] = max(nums[i], dp[i-1] + nums[i])。
  • 空间优化的动态规划法进一步优化了空间复杂度，只需要使用两个变量：currentSum表示当前的子数组和，maxSum表示全局的最大子数组和。