题解 | #最大子段和#

最大子段和

https://www.nowcoder.com/practice/f04519cd1d904f50b68f4229a126ab08

题目链接

最大子段和

题目描述

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

解题思路

本题是经典的动态规划问题，通常使用“Kadane算法”来高效解决。

我们定义 $dp[i]$ 为以数组中第 $i$ 个元素 $a[i]$ 结尾的连续子数组的最大和。我们的目标是求出所有 $dp[i]$ 中的最大值。

对于第 $i$ 个元素，以它结尾的最大和子数组有两种可能：

子数组只包含 $a[i]$ 这一个元素。
子数组是在以 $a[i-1]$ 结尾的最大和子数组后面，再接上 $a[i]$ 形成的。

因此，我们可以得到状态转移方程： $dp[i] = \max(a[i], dp[i-1] + a[i])$

这个方程的含义是：以 $a[i]$ 结尾的最大子数组和，要么是 $a[i]$ 本身（这意味着开启一个新的子数组），要么是 $a[i]$ 加上前一个元素结尾的最大子数组和（这意味着延续之前的子数组）。

我们只需要一个变量来记录全局的最大和。在遍历数组计算每个 $dp[i]$ 的同时，我们用一个全局最大值变量来更新和保留历史上的最大 $dp$ 值。

在实现时，可以发现计算 $dp[i]$ 只需要 $dp[i-1]$ 的值。因此，我们不需要一个完整的 $dp$ 数组，只需要一个变量来记录“当前结尾的最大和”即可，从而将空间复杂度优化到 $\mathcal{O}(1)$ 。

代码

c++
java
python

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

    // current_max 相当于 dp[i]，max_so_far 是全局最大值
    long long current_max = a[0];
    long long max_so_far = a[0];

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

    cout << max_so_far << "\n";

    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();
        }

        // currentMax 相当于 dp[i]，maxSoFar 是全局最大值
        long currentMax = a[0];
        long maxSoFar = a[0];

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

        System.out.println(maxSoFar);
    }
}

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

# current_max 相当于 dp[i]，max_so_far 是全局最大值
current_max = a[0]
max_so_far = a[0]

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

print(max_so_far)