小红的岁晚可可塔

[题目链接](https://www.nowcoder.com/practice/6b06f501f8154f57801590ca495f37ac)

思路

本题是经典的最大子数组和问题。给定 层蛋糕，每层有一个甜度值（可正可负），要求找到一段连续的蛋糕层，使得甜度值之和最大。

Kadane 算法

我们用贪心的思想来解决这个问题。维护一个变量 cur 表示以当前元素结尾的最大子数组和：

  1. 遍历数组，将当前元素加到 cur 上。
  2. 用 cur 更新全局答案 ans。
  3. 如果 cur < 0，说明前面的子数组对后续只有负贡献，不如从下一个元素重新开始，将 cur 置为 0。

关键点：先更新答案再判断是否重置。这样即使所有元素都是负数，也能正确选出最大的那个负数。

举例

以样例 [2, -4, 3, -1, 2, -4, 3] 为例：

位置 元素 cur ans
0 2 2 2
1 -4 -2→0 2
2 3 3 3
3 -1 2 3
4 2 4 4
5 -4 0→0 4
6 3 3 4

最终答案为 ，对应子数组 。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    long long cur = 0, ans = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        long long x;
        scanf("%lld", &x);
        cur += x;
        if (cur > ans) ans = cur;
        if (cur < 0) cur = 0;
    }
    printf("%lld\n", ans);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long cur = 0, ans = Long.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            cur += x;
            if (cur > ans) ans = cur;
            if (cur < 0) cur = 0;
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
cur = 0
ans = float('-inf')
for x in a:
    cur += x
    if cur > ans:
        ans = cur
    if cur < 0:
        cur = 0
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    let cur = 0, ans = -Infinity;
    for (let i = 0; i < n; i++) {
        cur += a[i];
        if (cur > ans) ans = cur;
        if (cur < 0) cur = 0;
    }
    console.log(ans);
});

复杂度分析

  • 时间复杂度：，只需遍历数组一次。
  • 空间复杂度：，只使用了常数个额外变量（C++ 解法甚至不需要存储整个数组）。