题解 | #小红的岁晚可可塔#

题目链接

小红的岁晚可可塔

题目描述

小红准备制作一个名为“岁晚可可塔”的甜品，由 $N$ 层巧克力蛋糕组成。每一层蛋糕都有一个甜度值 $a_i$ ：

如果 $a_i > 0$ ，表示这一层口感香甜。
如果 $a_i < 0$ ，表示这一层带有苦味。

为了保证口感的连贯性，小红需要从这 $N$ 层蛋糕中切出一段连续的非空区间 $[l, r]$ 作为最终成品，使得该段蛋糕的甜度总和最大。请帮小红计算出这连续的一段蛋糕层所能达到的最大甜度总和。

解题思路

本题是经典的**最大子数组和（Maximum Subarray Sum）**问题，可以使用 Kadane's 算法 在 $\mathcal{O}(N)$ 的时间复杂度内解决。

核心思想：遍历数组，维护一个当前子数组的最大和 $current\_sum$ 。对于每一个新元素 $a_i$ ，我们面临两个选择：
- 将 $a_i$ 加入到当前的子数组中： $current\_sum + a_i$ 。
- 以 $a_i$ 为起点开启一个新的子数组： $a_i$ 。因此，更新公式为： $current\_sum = \max(a_i, current\_sum + a_i)$ 。
维护全局最大值：在遍历过程中，不断更新全局最大值 $ans = \max(ans, current\_sum)$ 。
注意点：
- 题目要求区间必须是非空的。
- 甜度值 $a_i$ 的范围在 $[-10^9, 10^9]$ 之间， $N$ 最大为 $10^5$ ，因此总和可能超过 $2^{31}-1$ ，需要使用 64 位整数存储（C++ 中的 long long，Java 中的 long）。

代码

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];
    }

    // Kadane's 算法初始化
    long long current_sum = a[0];
    long long ans = a[0];

    for (int i = 1; i < n; ++i) {
        // 对于每一层，决定是接在前面的序列后面，还是重新开始
        current_sum = max(a[i], current_sum + a[i]);
        // 更新全局最大甜度总和
        ans = max(ans, current_sum);
    }

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

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

        // 初始化：ans 和 currentSum 都设为第一层的值
        long currentSum = a[0];
        long ans = a[0];

        for (int i = 1; i < n; i++) {
            // 状态转移：取当前值或当前值与之前和的累加值中的较大者
            currentSum = Math.max(a[i], currentSum + a[i]);
            // 更新结果
            ans = Math.max(ans, currentSum);
        }

        System.out.println(ans);
    }
}

def solve():
    # 读取输入
    n = int(input())
    a = list(map(int, input().split()))

    # Kadane's 算法
    # 初始化为第一个元素，确保区间非空
    current_sum = a[0]
    ans = a[0]

    for i in range(1, n):
        # 决定当前层是否加入前面的连续段
        if current_sum > 0:
            current_sum += a[i]
        else:
            current_sum = a[i]
        
        # 更新全局最大值
        if current_sum > ans:
            ans = current_sum
            
    print(ans)

solve()

算法及复杂度

算法：Kadane's 算法（动态规划）。
时间复杂度： $\mathcal{O}(N)$ 。只需对 $N$ 层蛋糕进行一次线性遍历。
空间复杂度： $\mathcal{O}(N)$ 。主要是用于存储 $N$ 层蛋糕甜度值的数组。若采用边读取边处理的方式，空间复杂度可优化至 $\mathcal{O}(1)$ 。