题解 | #最大子段和#

题目链接

最大子段和

题目描述

给定一个长度为 $n$ 的整数数组 $a$ 。请你从中选取一个非空子数组（连续的一段），使得其元素之和最大。求出该最大和。

输入:

第一行输入一个整数 $n$ ，代表数组的长度。
第二行输入 $n$ 个整数，代表数组元素。

输出:

一个整数，代表所能得到的最大子数组元素和。

解题思路

这是一个经典的算法问题，最优解法是使用Kadane算法，这是一种动态规划的思路。

定义状态: 我们定义 $dp[i]$ 为以第 $i$ 个元素 $a_i$ 结尾的子数组的最大和。注意这个定义的关键点：“以 $a_i$ 结尾”。
状态转移方程: 对于第 $i$ 个元素 $a_i$ ，要构成一个以它结尾的最大和子数组，我们只有两种选择：
- 自成一派: 这个子数组只包含 $a_i$ 本身。此时和就是 $a_i$ 。
- 加入组织: 将 $a_i$ 添加到以 $a_{i-1}$ 结尾的最大和子数组的末尾。此时和为 $dp[i-1] + a_i$ 。
我们在这两种选择中取较大者，便得到了以 $a_i$ 结尾的最大和： $dp[i] = \max(a_i, dp[i-1] + a_i)$ 这个方程的直观解释是：如果前一个子数组的和 $dp[i-1]$ 是一个负数，那么加上它只会让总和变小，还不如从 $a_i$ 开始一个新的子数组。
最终结果: 我们需要的结果是整个数组的最大子段和，它不一定以最后一个元素结尾。因此，最终答案应该是所有 $dp[i]$ ( $1 \le i \le n$ ) 中的最大值。
空间优化: 观察状态转移方程，我们发现计算 $dp[i]$ 只需要 $dp[i-1]$ 的值。因此，我们不需要一个完整的 $dp$ 数组。我们只需要两个变量：
- current_max：用于记录以当前元素结尾的最大子数组和（相当于 $dp[i]$ ）。
- global_max：用于记录到目前为止发现的全局最大子数组和（相当于 $\max(dp_1, \dots, dp_i)$ ）。
算法流程简化为：
- 初始化 current_max 和 global_max 都为数组的第一个元素。
- 从第二个元素开始遍历数组：
  - 更新 current_max: current_max = max(a[i], current_max + a[i])。
  - 更新 global_max: global_max = max(global_max, current_max)。
- 遍历结束后，global_max 就是答案。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    long long current_max = a[0];
    long long global_max = a[0];

    for (int i = 1; i < n; ++i) {
        current_max = max(a[i], current_max + a[i]);
        if (current_max > global_max) {
            global_max = current_max;
        }
    }

    cout << global_max << endl;

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        long currentMax = a[0];
        long globalMax = a[0];

        for (int i = 1; i < n; i++) {
            currentMax = Math.max(a[i], currentMax + a[i]);
            if (currentMax > globalMax) {
                globalMax = currentMax;
            }
        }

        System.out.println(globalMax);
    }
}

n = int(input())
a = list(map(int, input().split()))

current_max = a[0]
global_max = a[0]

for i in range(1, n):
    current_max = max(a[i], current_max + a[i])
    if current_max > global_max:
        global_max = current_max

print(global_max)

算法及复杂度

算法：动态规划 (Kadane's Algorithm)
时间复杂度： $\mathcal{O}(n)$ - 我们只需要对数组进行一次线性遍历。
空间复杂度： $\mathcal{O}(n)$ - 主要用于存储输入的 $n$ 个元素。Kadane算法本身的空间复杂度是 $\mathcal{O}(1)$ 。