文章目录
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(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，就更新max
if(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)，适用于解决大型数组的最大子数组和问题。
