题目链接

连续子数组最大和

题目描述

输入一个整型数组（数组里可能有正数、负数和零），求其中一个连续子数组（最少包含一个元素）的和的最大值。

要求时间复杂度为 。

解题思路

这是一个非常经典的算法问题，最优解法是使用动态规划或一种称为“Kadane's Algorithm”的在线处理思想，可以在一次遍历中解决问题。

核心思想：

我们从头到尾遍历数组，同时维护两个变量：

  1. current_max：表示以当前元素结尾的连续子数组的最大和。
  2. global_max：表示到目前为止，在所有子数组中发现的最大和，也就是我们最终的答案。

状态转移逻辑：

当我们遍历到数组的第 i 个元素 a[i] 时，我们思考如何更新 current_max。

  • 对于以 a[i] 结尾的这个子数组，它要么是 a[i] 自己单独构成，要么是 a[i] 连接在“以 a[i-1] 结尾的最大和子数组”的后面。
  • 因此，current_max 的更新规则是：current_max = max(a[i], current_max + a[i])。

这个规则背后有一个更直观的理解：

  • 我们用 current_max 来累加当前连续子数组的和。
  • 如果在累加过程中，current_max 的值变成了负数，那么它对于后续任何元素的累加都只会产生负贡献（即拖后腿）。
  • 此时，任何一个从下一个元素开始的新子数组，都会比“一个负数 + 新元素”的和要大。
  • 所以，一旦 current_max 变为负数，我们就应该果断地“抛弃”它，并将其重置为0，相当于从下一个元素开始，重新寻找一个新的、可能成为最大和的子数组。

算法步骤：

  1. 初始化 global_max 为数组的第一个元素（或一个极小的负数），current_max 为 0。
  2. 遍历数组中的每一个元素 x： a. 将 x 累加到 current_max 上。 b. 用 current_max 的值更新 global_max：global_max = max(global_max, current_max)。 c. 如果 current_max 变为负数，则将其重置为 0。
  3. 遍历结束后，global_max 中存储的就是最终的答案。

这个算法巧妙地在 时间复杂度和 空间复杂度内解决了问题。

代码

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

using namespace std;

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

    int n;
    cin >> n;

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    // 读取第一个数用于初始化
    long long val;
    cin >> val;

    long long global_max = val;
    long long current_max = val;
    
    // 如果第一个数是负数，则当前和可以从0开始算
    if (current_max < 0) {
        current_max = 0;
    }

    for (int i = 1; i < n; ++i) {
        cin >> val;
        current_max += val;
        global_max = max(global_max, current_max);
        if (current_max < 0) {
            current_max = 0;
        }
    }

    cout << global_max << endl;

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

        if (n == 0) {
            System.out.println(0);
            return;
        }

        // 读取第一个数用于初始化
        long val = sc.nextLong();
        long globalMax = val;
        long currentMax = val;

        // 如果第一个数是负数，则当前和可以从0开始算
        if (currentMax < 0) {
            currentMax = 0;
        }

        for (int i = 1; i < n; i++) {
            val = sc.nextLong();
            currentMax += val;
            globalMax = Math.max(globalMax, currentMax);
            if (currentMax < 0) {
                currentMax = 0;
            }
        }

        System.out.println(globalMax);
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        
        if n == 0:
            print(0)
            return

        nums = []
        for _ in range(n):
            line = sys.stdin.readline()
            if line:
                nums.append(int(line.strip()))
        
        if not nums:
            print(0)
            return

        global_max = nums[0]
        current_max = nums[0]
        
        if current_max < 0:
            current_max = 0

        for i in range(1, n):
            current_max += nums[i]
            global_max = max(global_max, current_max)
            if current_max < 0:
                current_max = 0
        
        print(global_max)
        
    except (IOError, ValueError):
        return

solve()

算法及复杂度

  • 算法：动态规划 / Kadane's Algorithm

  • 时间复杂度: ，因为我们只需要对数组进行一次线性遍历。

  • 空间复杂度: ，我们只使用了有限的几个变量来存储状态，与输入数组的大小无关。