leetcode HOT100随笔 #053. 最大子数组和

目录

题干：

思考：

暴力解题解：

遍历数组每个位置做一次贪心决策

完整动态规划写法：

题干：

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

示例 ：

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

进阶：如果你已经实现复杂度为O(n)的解法，尝试使用更为精妙的分治法求解。

思考：

暴力解：两层for循环遍历，第一层设置cur重置

暴力解题解：

class Solution { public: int maxSubArray(vector<int>& nums) { int ans = INT_MIN; for (int i = 0; i < nums.size(); i++) { int cur = 0; for (int j = i; j < nums.size(); j++) { cur = cur + nums[j]; ans = max(ans, cur); } } return ans; } };

显然不能AC

遍历数组每个位置做一次贪心决策：

如果把之前的加上变得更小了->之前的拖累->扔掉前面的重新开始cur=nums[i]

如果把之前的加上更大了->之前的可以要->cur=cur+nums[i]

class Solution { public: int maxSubArray(vector<int>& nums) { int cur=nums[0]; int ans=nums[0]; for(int i=1;i<nums.size();i++){ cur=max(nums[i],cur+nums[i]); // 每次选择重新开始or和之前续上 ans=max(ans,cur); } return ans; } };

时间O(n)，空间O(1)

完整动态规划写法：

class Solution { public: int maxSubArray(vector<int>& nums) { vector<int> dp(nums.size()); dp[0] = nums[0]; for(int i=1;i<nums.size();i++){ dp[i] = max(nums[i],dp[i-1]+nums[i]); // 动态规划每一步的最大值都存入dp中 } return *max_element(dp.begin(),dp.end()); // 解引用取出数组dp中存的最大值 } };