题目链接

最大子段和

题目描述

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

解题思路

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

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

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

  1. 子数组只包含 这一个元素。
  2. 子数组是在以 结尾的最大和子数组后面，再接上 形成的。

因此，我们可以得到状态转移方程：

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

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

在实现时，可以发现计算 只需要 的值。因此，我们不需要一个完整的 数组，只需要一个变量来记录“当前结尾的最大和”即可，从而将空间复杂度优化到 。

代码

#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)

算法及复杂度

  • 算法：动态规划（Kadane算法）
  • 时间复杂度：，因为我们只需要对数组进行一次遍历。
  • 空间复杂度：，我们只使用了常数个额外变量来存储状态。