去哪里找做网站 的客户模板网站建设教程

53. 最大子数组和

题目描述

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

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 10⁵
• -104 <= nums[i] <= 10⁴

暴力（运行超时）

// 引入必要的头文件
class Solution {
public:// maxSubArray函数接受一个整数型向量nums作为参数，并返回一个整数int maxSubArray(vector<int>& nums) {// 初始化max为INT_MIN，这表示最小可能的整数，确保任何元素的和都会大于它int max=INT_MIN;// 外层循环遍历数组的每个元素，作为子数组的起点for(int i=0;i<nums.size();i++){// 初始化num为0，它将用来存储从索引i开始的子数组的和int num=0;// 内层循环从i开始遍历数组，每次循环都会增加子数组的长度for(int j=i;j<nums.size();j++){// 将当前元素累加到num上num+=nums[j];// 如果当前的num大于已知的最大值max，就更新maxif(max<num)max=num;}}// 循环结束后，max就是所有子数组和的最大值，返回这个值return max;}
};

这段代码使用了简单直观的暴力方法来求解问题，即尝试数组中所有可能的子数组，并记录下具有最大和的值。这个方法的时间复杂度是O(n^2)，因为它使用了两层嵌套循环来遍历所有可能的子数组。这种方法在数组长度非常大时可能会非常慢，但对于较小的数组，它是足够工作的。

贪心

// 包含必要的头文件
#include<vector>
#include<climits> // 用于INT_MIN，代表最小可能的整数
using namespace std;// 定义Solution类，此类包含解决问题的方法
class Solution {
public:// maxSubArray方法接收一个引用传递的整数向量nums，并返回一个整数int maxSubArray(vector<int>& nums) {// 初始化max为INT_MIN，它将记录目前为止遇到的最大子数组和int max=INT_MIN;// 初始化count为0，它将用来计算当前考虑的子数组的和int count=0;// 遍历数组中的每个元素for(int i=0;i<nums.size();i++){// 将当前元素加到count上count+=nums[i];// 如果count大于max，则更新max为count的值if(max<count) max=count;// 如果count小于0，则重置count为0，因为任何包含负和前缀的子数组都不可能构成最大子数组if(count<0) count=0;}// 遍历完成后，max将包含最大子数组和，返回这个值return max;}
};

如果当前子数组和变为负数，那么它不会对结果有帮助，因此将其重置为0。这个实现假定数组中至少有一个正数，这是因为max的初始值是INT_MIN，即使数组中所有数字都是负数，算法也会返回最大的负数。

这个算法的优点是空间复杂度低，因为它只使用了常数空间，并且时间复杂度为O(n)，适用于解决大型数组的最大子数组和问题。