c++ 子数组动态规划问题
1.最大子数组和 力扣
给你一个整数数组
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
-
class Solution {
-
const int INF=0x3f3f3f3f;
-
public:
-
int maxSubArray(vector<int>& nums)
-
{
-
int n=nums.size();
-
vector<int> dp(n 1);
-
int ret=-INF;
-
for(int i=1;i<=n;i )
-
{
-
dp[i]=max(nums[i-1],dp[i-1] nums[i-1]);
-
ret=max(ret,dp[i]);//不能从dp[0]开始找,从dp[1]开始找
-
}
-
-
return ret;
-
}
-
};
2.环形子数组最大和 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
给定一个长度为
n
的环形整数数组nums
,返回nums
的非空 子数组 的最大可能和 。环形数组 意味着数组的末端将会与开头相连呈环状。形式上,
nums[i]
的下一个元素是nums[(i 1) % n]
,nums[i]
的前一个元素是nums[(i - 1 n) % n]
。子数组 最多只能包含固定缓冲区
nums
中的每个元素一次。形式上,对于子数组nums[i], nums[i 1], ..., nums[j]
,不存在i <= k1, k2 <= j
其中k1 % n == k2 % n
。示例 1:
输入:nums = [1,-2,3,-2] 输出:3 解释:从子数组 [3] 得到最大和 3
示例 2:
输入:nums = [5,-3,5] 输出:10 解释:从子数组 [5,5] 得到最大和 5 5 = 10
示例 3:
输入:nums = [3,-2,2,-3] 输出:3 解释:从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
-
class Solution {
-
const int INF = 0x3f3f3f3f;
-
public:
-
int maxSubarraySumCircular(vector<int>& nums)
-
{
-
int n = nums.size();
-
int sum = 0;
-
for (auto sh : nums) sum = sh;
-
vector<int> f(n 1);//找最大值
-
vector<int> g(n 1);//找最小值
-
-
int retmax = -INF;
-
int retmin = INF;
-
-
for (int i = 1; i <= n; i )
-
{
-
f[i] = max(nums[i - 1], f[i - 1] nums[i - 1]);
-
retmax = max(retmax, f[i]);
-
-
g[i] = min(nums[i - 1], g[i - 1] nums[i - 1]);
-
retmin = min(retmin, g[i]);
-
}
-
-
/*if(sum-retmin==0)
-
return retmax;
-
return retmax == retmin ? retmax : max(retmax, sum - retmin);*/
-
return retmax == retmin ? retmax : max(retmax, sum - retmin==0?retmax:sum-retmin);
-
}
-
};
-
3.乘积最大子数组 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
给你一个整数数组
nums
,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
-
class Solution {
-
public:
-
int maxProduct(vector<int>& nums)
-
{
-
int n=nums.size();
-
vector<int> f(n 1);
-
auto g=f;
-
int ret=INT_MIN;
-
int retmin=INT_MAX;
-
-
f[0]=g[0]=1;
-
-
-
for(int i=1;i<=n;i )
-
{
-
f[i]=max(nums[i-1],max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));
-
ret=max(ret,f[i]);//不能从dp[0]开始找,从dp[1]开始找
-
g[i]=min(nums[i-1],min(g[i-1]*nums[i-1],f[i-1]*nums[i-1]));
-
retmin=min(retmin,g[i]);
-
}
-
-
return ret;
-
}
-
};
4.成绩为正数的最长子数组长度 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
给你一个整数数组
nums
,请你求出乘积为正数的最长子数组的长度。一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例 1:
输入:nums = [1,-2,-3,4] 输出:4 解释:数组本身乘积就是正数,值为 24 。
示例 2:
输入:nums = [0,1,-2,-3,-4] 输出:3 解释:最长乘积为正数的子数组为 [1,-2,-3] ,乘积为 6 。 注意,我们不能把 0 也包括到子数组中,因为这样乘积为 0 ,不是正数。
示例 3:
输入:nums = [-1,-2,-3,0,1] 输出:2 解释:乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3]
-
class Solution {
-
public:
-
int getMaxLen(vector<int>& nums)
-
{
-
int n=nums.size();
-
vector<int> f(n 1);
-
auto g=f;
-
-
int ret=INT_MIN;
-
for(int i=1;i<=n;i )
-
{
-
if(nums[i-1]>0)//正数
-
{
-
f[i]=f[i-1] 1;
-
g[i]=g[i-1]==0?0:g[i-1] 1;
-
}
-
else if(nums[i-1]<0)//负数
-
{
-
f[i]=g[i-1]==0?0:g[i-1] 1;
-
g[i]=f[i-1] 1;
-
}
-
ret=max(ret,f[i]);
-
}
-
return ret;
-
}
-
};
5.等差数列划分 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
如果一个数列 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该数列为等差数列。
- 例如,
[1,3,5,7,9]
、[7,7,7,7]
和[3,-1,-5,-9]
都是等差数列。给你一个整数数组
nums
,返回数组nums
中所有为等差数组的 子数组 个数。子数组 是数组中的一个连续序列。
示例 1:
输入:nums = [1,2,3,4] 输出:3 解释:nums 中有三个子等差数组:[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2:
输入:nums = [1] 输出:0
-
class Solution {
-
public:
-
int numberOfArithmeticSlices(vector<int>& nums)
-
{
-
int n=nums.size();
-
int dp[2]={0};
-
int sum=0;
-
for(int i=2;i<n;i )
-
{
-
-
dp[i%2]=nums[i]-nums[i-1]==nums[i-1]-nums[i-2]?dp[(i-1)%2] 1:0;
-
-
sum =dp[i%2];
-
}
-
return sum;
-
}
-
};
6.最长湍流子数组 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
给定一个整数数组
arr
,返回arr
的 最大湍流子数组的长度 。如果比较符号在子数组中的每个相邻元素对之间翻转,则该子数组是 湍流子数组 。
更正式地来说,当
arr
的子数组A[i], A[i 1], ..., A[j]
满足仅满足下列条件时,我们称其为湍流子数组:
- 若
i <= k < j
:
- 当
k
为奇数时,A[k] > A[k 1]
,且- 当
k
为偶数时,A[k] < A[k 1]
;- 或 若
i <= k < j
:
- 当
k
为偶数时,A[k] > A[k 1]
,且- 当
k
为奇数时,A[k] < A[k 1]
。示例 1:
输入:arr = [9,4,2,10,7,8,8,1,9] 输出:5 解释:arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
示例 2:
输入:arr = [4,8,12,16] 输出:2
示例 3:
输入:arr = [100] 输出:1
-
class Solution {
-
public:
-
int maxTurbulenceSize(vector<int>& arr)
-
{
-
int n=arr.size();
-
vector<int> f(n,1);
-
auto g=f;
-
int ret=1;
-
for(int i=1;i<n;i )
-
{
-
if(arr[i]>arr[i-1])
-
{
-
f[i]=g[i-1] 1;
-
}
-
else if(arr[i]<arr[i-1])
-
{
-
g[i]=f[i-1] 1;
-
}
-
ret=max(ret,max(g[i],f[i]));
-
}
-
return ret;
-
}
-
};
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbcia
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13