数据结构和算法面试题：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

GeekLiHua

发布于 2025-01-21 14:53:36

5330

文章被收录于专栏：JavaJava

数据结构和算法面试题：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

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

该算法的实现思路如下：

使用一个变量ans存储最终的答案，使用一个变量cur存储当前的连续子数组和。
遍历整个数组，对于每一个数字，更新cur为它自身和(cur + nums[i])之间的较大值。如果cur大于ans，则将ans更新为cur。
遍历完数组后，返回ans作为最大子数组和。

下面是使用C++实现查找最大子数组和的代码，并附带详细注释：

#include <iostream>
#include <vector>

using namespace std;

int maxSubArray(vector<int>& nums) {
    int ans = nums[0]; // 初始化最终答案
    int cur = nums[0]; // 初始化当前连续子数组

    for (int i = 1; i < nums.size(); ++i) {
        cur = max(nums[i], cur + nums[i]); // 更新当前连续子数组和
        ans = max(ans, cur); // 更新最终答案
    }

    return ans;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int ans = maxSubArray(nums);
    cout << ans << endl; // 6
    return 0;
}

该算法遍历整个数组，维护了两个变量ans和cur，其中ans表示目前找到的最优连续子序列的和，cur是num[i]为结尾的连续子数组的和。在每次遍历中，用当前数值num[i]与num[i]+cur之间的较大值更新cur并求出当前子数组msum[i]的和，将其与ans作比较，并记录在ans中；最终返回ans作为答案。由于只有一层循环，该算法的时间复杂度为 O(n)。

java版本

import java.util.Arrays;

public class Main {
    public static int maxSubArray(int[] nums) {
        int ans = nums[0]; // 初始化最终答案
        int cur = nums[0]; // 初始化当前连续子数组

        for (int i = 1; i < nums.length; ++i) {
            cur = Math.max(nums[i], cur + nums[i]); // 更新当前连续子数组和
            ans = Math.max(ans, cur); // 更新最终答案
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int ans = maxSubArray(nums);
        System.out.println(ans); // 6
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-20，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历