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

【动态规划】子数组系列（一）

backend 2025/7/30 1:37:40

📝前言说明：

本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

你可以点击下方链接，进行不同专题的动态规划的学习

点击链接	开始学习
斐波那契数列模型	路径问题
简单多状态（一）	简单多状态（二）
子数组系列（一）	子数组系列（二）
子序列问题（一）	子序列问题（二）
回文串问题	两个数组dp问题（一）
两个数组的dp问题（二）	01背包问题
完全背包	二维的背包问题
其他

题目

53. 最大子数组和
- 个人解
918. 环形子数组的最大和
- 优质解
152. 乘积最大子数组
- 优质解
1567. 乘积为正数的最长子数组长度
- 个人解

53. 最大子数组和

题目链接：https://leetcode.cn/problems/maximum-subarray/description/
在这里插入图片描述

个人解

思路：

dp[i]：以 i 位置为结尾的所有子数组中的最大子数组和【没要求子数组的开头从 0 开始】
状态转移：以i位置为结尾的所有子数组可以分成两类
- 一类：元素个数1
- 另一类：元素个数>1（而对于元素个数 >1 的子数组，不看i位置的元素，它们都是以i - 1位置结尾的子数组）
所以可以推出状态转移方程：dp[i] = max(nums[i], dp[i - 1] + nums[i])
初始化：dp[0] = nums[0]
填表顺序：从左往右
返回值：遍历一遍，找到最大值

用时：10:00
屎山代码：

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 0);dp[0] = nums[0];int ans = nums[0];for(int i = 1; i < n; i++){dp[i] = max(nums[i], nums[i] + dp[i - 1]);if(dp[i] > ans)ans = dp[i]; // 同时记录出现的最大值}return ans;}
};

时间复杂度：O(n)
空间复杂度：O(n)

918. 环形子数组的最大和

题目链接：https://leetcode.cn/problems/maximum-sum-circular-subarray/description/
在这里插入图片描述

优质解

思路：

我们的子数组的形态有两种：首位不想连，首位相连。
对于首位不想连，和上一题一样。
对于首位相连的子数组，则数组中间必有连续的一段是空出来的，而这一段一定是数组的最小和连续子数组，通过数组所有元素的和减去这一段最小和：sum - gmin就可以得到最大和。

代码：

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();vector<int> dp_max(n, 0);auto dp_min = dp_max;dp_max[0] = nums[0];dp_min[0] = nums[0];int gmax = nums[0], gmin = nums[0], sum = nums[0];for(int i = 1; i < n; i++){sum += nums[i];dp_max[i] = max(nums[i], dp_max[i - 1] + nums[i]);gmax = max(gmax, dp_max[i]);dp_min[i] = min(nums[i], dp_min[i - 1] + nums[i]);gmin = min(gmin, dp_min[i]);}return gmin == sum ? gmax : max(gmax, sum - gmin); // 防止一下全是负数}
};

时间复杂度：O(n)
空间复杂度：O(n)

152. 乘积最大子数组

题目链接：https://leetcode.cn/problems/maximum-product-subarray/description/
在这里插入图片描述

优质解

思路：

dp[i] = max(nums[i], dp[i - 1] * nums[i])不行，因为有正负号的问题
- 前面的最小值，有可能因为后面的数是负数，而变成最大值
所以我们可以多记录最小值，在进行dp更新的时候，还要依据最小值的表

代码：

class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();vector<int> dp_max(n, 0);auto dp_min = dp_max;dp_max[0] = nums[0]; dp_min[0] = nums[0];int ans = nums[0];for(int i = 1; i < n; i++){if(nums[i] >= 0){dp_max[i] = max(nums[i], dp_max[i - 1] * nums[i]);dp_min[i] = min(nums[i], dp_min[i - 1] * nums[i]);}else{dp_max[i] = max(nums[i], dp_min[i - 1] * nums[i]);dp_min[i] = min(nums[i], dp_max[i - 1] * nums[i]);}ans = max(ans, dp_max[i]);}return ans;}
};

时间复杂度：O(n)
空间复杂度：O(n)

1567. 乘积为正数的最长子数组长度

题目链接：https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/description/
在这里插入图片描述

个人解

思路：

开一个最长的正的，开一个最长的负的
注意一些细节问题

用时：10:00
屎山代码：

class Solution {
public:int getMaxLen(vector<int>& nums) {int n = nums.size();vector<int> dp_po(n, 0);auto dp_ne = dp_po;if(nums[0] != 0)nums[0] > 0? dp_po[0] = 1: dp_ne[0] = 1;int ans = dp_po[0];for(int i = 1; i < n; i++){if(nums[i] > 0){dp_po[i] = dp_po[i - 1] + 1;dp_ne[i] = dp_ne[i - 1] > 0 ? dp_ne[i - 1] + 1 : 0; // +1 的前提是已经有子数组了（即长度不为 0 ）}else if(nums[i] < 0){dp_po[i] = dp_ne[i - 1] > 0? dp_ne[i - 1] + 1 : 0;dp_ne[i] = dp_po[i - 1] + 1;}else{dp_ne[i] = dp_po[i] = 0;}ans = max(ans, dp_po[i]);}return ans;}
};