当前位置：首页 > article >正文

LeetCode 热题 100_最大子数组和(13_53)（贪心算法 ||动态规划）

article 2024/11/29 8:40:54

LeetCode 热题 100_最大子数组和（13_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⁵
-10⁴ <= nums[i] <= 10⁴

题解：

解题思路：

思路一（暴力求解）：
枚举所有的子数组，记录最大子数组和。

思路二（贪心算法 ||动态规划）：
1、题目要求最大子数组和，首先分析出子数组是一个连续的区间，要求最大的子数组和，进而想到贪心算法和动态规划的思想。

2、具体思路如下：
① 如果前边的和大于0则累加
② 如果前边的和<=0则舍弃
③ 更新前边的和

例：nums = [-2,1,-3,4,-1,2,1,-5,4]
[[-2],1,-3,4,-1,2,1,-5,4] pre_sum=0则丢弃，更新pre_sum=-2，记录当前最大子数组和max=-2。
[-2,[1],-3,4,-1,2,1,-5,4] pre_sum=-2<0则丢弃，更新pre_sum=1，记录当前最大子数组和max=1。
[-2,1,[-3],4,-1,2,1,-5,4] pre_sum=1>0累加，更新pre_sum=-2，记录当前最大子数组和max=1。
[-2,1,-3,[4],-1,2,1,-5,4] pre_sum=-2<0则丢弃，更新pre_sum=4，记录当前最大子数组和max=4。
…
力扣官方题解感觉不错，浅显易懂

3、复杂度分析
① 时间复杂度：O(N)，其中 N 是数组中的元素数量。因遍历一遍数组一次。
② 空间复杂度：O(1)，我们只需要常数空间存放若干变量。

4、一位码友总结的很好：“ 走完这一生如果我和你在一起会变得更好，那我们就在一起，否则我就丢下你。我回顾我最光辉的时刻就是和不同人在一起，变得更好的最长连续时刻。”

代码实现（思路二（贪心算法 ||动态规划））：

#include<iostream>
#include<vector>
using namespace std;
int maxSubArray1(vector<int>& nums) {
	int max=INT_MIN;
	//存放之前和 
	int pre_sum=0;
	for(const auto &num:nums){
		//之前和>0则累加 
		if(pre_sum>0){  //这里pre_sum是之前和 
			pre_sum+=num;  //在这里是现在和 
		//之前和<0则丢弃 
		} else{
			pre_sum=num;
		} 
		if(max<pre_sum){
			max=pre_sum;
		}
	} 
    return max;
}

int main(){
	vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
	cout<<maxSubArray1(nums);	
	return 0;
}