网站开发后端做那些,学习建设网站难么,版面设计软件,.net 创建网站项目文章目录 53. 最大子数组和题目描述暴力#xff08;运行超时#xff09;贪心 53. 最大子数组和
题目描述
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组是数组… 文章目录 53. 最大子数组和题目描述暴力运行超时贪心 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 105-104 nums[i] 104
暴力运行超时
// 引入必要的头文件
class Solution {
public:// maxSubArray函数接受一个整数型向量nums作为参数并返回一个整数int maxSubArray(vectorint nums) {// 初始化max为INT_MIN这表示最小可能的整数确保任何元素的和都会大于它int maxINT_MIN;// 外层循环遍历数组的每个元素作为子数组的起点for(int i0;inums.size();i){// 初始化num为0它将用来存储从索引i开始的子数组的和int num0;// 内层循环从i开始遍历数组每次循环都会增加子数组的长度for(int ji;jnums.size();j){// 将当前元素累加到num上numnums[j];// 如果当前的num大于已知的最大值max就更新maxif(maxnum)maxnum;}}// 循环结束后max就是所有子数组和的最大值返回这个值return max;}
};这段代码使用了简单直观的暴力方法来求解问题即尝试数组中所有可能的子数组并记录下具有最大和的值。这个方法的时间复杂度是O(n^2)因为它使用了两层嵌套循环来遍历所有可能的子数组。这种方法在数组长度非常大时可能会非常慢但对于较小的数组它是足够工作的。
贪心
// 包含必要的头文件
#includevector
#includeclimits // 用于INT_MIN代表最小可能的整数
using namespace std;// 定义Solution类此类包含解决问题的方法
class Solution {
public:// maxSubArray方法接收一个引用传递的整数向量nums并返回一个整数int maxSubArray(vectorint nums) {// 初始化max为INT_MIN它将记录目前为止遇到的最大子数组和int maxINT_MIN;// 初始化count为0它将用来计算当前考虑的子数组的和int count0;// 遍历数组中的每个元素for(int i0;inums.size();i){// 将当前元素加到count上countnums[i];// 如果count大于max则更新max为count的值if(maxcount) maxcount;// 如果count小于0则重置count为0因为任何包含负和前缀的子数组都不可能构成最大子数组if(count0) count0;}// 遍历完成后max将包含最大子数组和返回这个值return max;}
};如果当前子数组和变为负数那么它不会对结果有帮助因此将其重置为0。这个实现假定数组中至少有一个正数这是因为max的初始值是INT_MIN即使数组中所有数字都是负数算法也会返回最大的负数。
这个算法的优点是空间复杂度低因为它只使用了常数空间并且时间复杂度为O(n)适用于解决大型数组的最大子数组和问题。
