笔试时间：2025年8月30日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：最大子序列和

给定一个整数数组，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

样例输入

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

样例输出

6

参考题解

维护两个量：cur：以当前元素结尾的子数组最大和，cur = max(x, cur + x)max：遍历到目前为止的全局最大和，max = max(max, cur)逐个元素更新上述两个量；当之前的累计和为负时，会自动“舍弃”，从当前元素重新开始。初始化 max 为首元素，cur 从 0 开始，保证全为负数时也能返回最大（最不小的）那个数。

C++：

#include <iostream>
#include <vector>
#include <algorithm>  // 用于 std::max

using namespace std;

// 计算最大子数组和（Kadane算法）
int maxSubArray(vector<int>& nums) {
    // 处理边界：若数组为空（原Java未处理，此处可选增强鲁棒性）
    if (nums.empty()) {
        return 0;  // 或抛出异常，根据需求调整
    }
    
    // 初始化全局最大值为数组第一个元素，当前子数组和为0
    int max_sum = nums[0];
    int current_sum = 0;
    
    // 遍历数组每个元素
    for (int x : nums) {
        // 关键逻辑：要么从当前元素重新开始，要么继续累加当前子数组
        current_sum = max(x, current_sum + x);
        // 更新全局最大值
        max_sum = max(max_sum, current_sum);
    }
    
    return max_sum;
}

// 测试示例（可选）
int main() {
    vector<int> test_nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << maxSubArray(test_nums1) << endl;  // 输出：6
    
    vector<int> test_nums2 = {1};
    cout << maxSubArray(test_nums2) << endl;  // 输出：1
    
    vector<int> test_nums3 = {5, 4, -1, 7, 8};
    cout << maxSubArray(test_nums3) << endl;  // 输出：23
    
    return 0;
}

Java：

import java.util.*;

public class Solution {
    public int maxSubArray (int[] nums) {
        int max = nums[0];
        int cur = 0;
        for (int x : nums) {
            cur = Math.max(x, cur + x);
            max = Math.max(max, cur);
        }
        return max;
    }
}

Python：

def max_sub_array(nums):
    # 处理边界：若数组为空（按原Java逻辑默认nums非空，此处可加判断增强鲁棒性）
    if not nums:
        return 0  # 或根据需求抛出异常，原Java未处理空数组，此处可选
    
    # 初始化全局最大值为数组第一个元素，当前子数组和为0
    max_sum = nums[0]
    current_sum = 0
    
    # 遍历数组每个元素
    for x in nums:
        # 关键逻辑：要么从当前元素重新开始累加，要么继续累加当前子数组
        current_sum = max(x, current_sum + x)
        # 更新全局最大值
        max_sum = max(max_sum, current_sum)
    
    return max_sum


# 测试示例（可选）
if __name__ == "__main__":
    test_nums1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]