【OJ】动归练习五之子组串
个人主页 ： zxctscl 如有转载请先通知
题目
- 1. 53. 最大子数组和
- 1.1 分析
- 1.2 代码
- 2. 918. 环形子数组的最大和
- 2.1 分析
- 2.2 代码
- 3. 152. 乘积最大子数组
- 3.1 分析
- 3.2 代码
- 4. 1567. 乘积为正数的最长子数组长度
- 4.1 分析
- 4.2 代码
1. 53. 最大子数组和
1.1 分析
一、题目解析： 求子数组最大和，可能会有所有元素和和子数组所有的和比较，然后取最大的一个。
二、算法原理：
- 状态表示 以i位置为结尾，来求子数组最大和。 dp[i]：表示以i位置为结尾所有字数组中的最大和
- 状态转移方程 那么dp[i]就可能分两种情况：一种就是只有一个数，就是i对应的nums[i];另一种情况就是不止一个数就是i-1最大的子数组和dp[i-1]加上i位置对应的nums[i]。然后取这两种情况的最大值。 状态转移方程：dp[i]=max(nums[i],dp[i-1]+nums[i])
- 初始化 第一位置的值可能也会取到，那么就多开一个空间，把dp[0]位置初始化为0，从而不影响后面的最大和。这里同时也要注意下标的映射关系，多开了一个空间,那么对应nums[i]的位置就得向前挪一个。
- 填表顺序 从左往右
- 返回值 就返回dp表中最大的值。 为了方便，先记录一下当前位置最大子序列和最大值，然后更新。
1.2 代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n=nums.size();
vector<int> dp(n+1);
dp[0]=0;
int ret=INT_MIN;
for(int i=1;i<=n;i++)
{
dp[i]=max(nums[i-1],dp[i-1]+nums[i-1]);
ret=max(ret,dp[i]);
}
return ret;
}
};2. 918. 环形子数组的最大和
2.1 分析
一、题目解析： 这个题与上面一个类似，就是变成了环形。那么这里就可以分为两类：一类是中间相连子数组求最大和；另一类是在结尾和开头求最大和，这里会不方便计算，那么就过来，求中间连续子数组最小和，然后用这个数组的和减去这个最小和，就是这段首尾的最大和。然后比较这两类的和大小，返回最大的那个值就可以了。
二、算法原理：
- 状态表示 以i位置为结尾，分两种情况：一种来求子数组最大和，一种求最小和 f[i]：表示以i位置为结尾所有字数组中的最大和 g[i]：表示以i位置为结尾所有字数组中的最小和
- 状态转移方程 那么f[i]就可能分两种情况：一种就是只有一个数，就是i对应的nums[i];另一种情况就是不止一个数就是i-1最大的子数组和f[i-1]加上i位置对应的nums[i]。然后取这两种情况的最大值。 f[i]：状态转移方程：f[i]=max(nums[i],f[i-1]+nums[i])
那么g[i]也可能分两种情况：一种就是只有一个数，就是i对应的nums[i];另一种情况就是不止一个数就是i-1最小的子数组和g[i-1]加上i位置对应的nums[i]。然后取这两种情况的最小值。 f[i]：状态转移方程：g[i]=min(nums[i],g[i-1]+nums[i])
- 初始化 第一位置的值可能也会取到，那么就多开一个空间，把f[0]位置和g[0]初始化为0，从而不影响后面的最大和。这里同时也要注意下标的映射关系，多开了一个空间,那么对应nums[i]的位置就得向前挪一个。
- 填表顺序 从左往右
- 返回值 一类是在f表中找到最大值fmax 一类是在g表中找到最小值gmin 但是在g表中可能会存在全是负数序列的情况，这里就得加一个判断，如果sum=gmin，那么就返回fmax，不然就比较两类和的大小，返回大的那一个。
2.2 代码
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
vector<int> f(n+1),g(n+1);
int fmax=INT_MIN,sum=0,gmin=INT_MAX;
for(int i=1;i<=n;i++)
{
f[i]=max(nums[i-1],f[i-1]+nums[i-1]);
fmax=max(fmax,f[i]);
g[i]=min(nums[i-1],g[i-1]+nums[i-1]);
gmin=min(gmin,g[i]);
sum+=nums[i-1];
}
return sum==gmin?fmax:max(fmax,sum-gmin);
}
};3. 152. 乘积最大子数组
3.1 分析
一、题目解析： 求子数组最大乘积，可能会有所有元素和和子数组所有的和比较，然后取最大的一个。但是可能会存在i位置小于0，所以的多加一个数组。
二、算法原理：
- 状态表示 以i位置为结尾，来求子数组乘积。 f[i]：表示以i位置为结尾所有字数组中的最大乘积 g[i]：表示以i位置为结尾所有字数组中的最小乘积
- 状态转移方程 那么f[i]就可能分两种情况：一种就是只有一个数，就是i对应的nums[i];另一种情况就是不止一个数就是i-1最大的子数组乘积f[i-1]乘i位置对应的nums[i]，但是这里的nums[i]可能是小于0,所以这里还得分两种情况：一个是nums[i]>0,那么就是最大的子数组乘积f[i-1]乘i位置对应的nums[i]；如果nums[i]<0,就是最小的子数组乘积g[i-1]乘i位置对应的nums[i]。然后取这两种情况的最大值。
g[i]就可能分两种情况：一种就是只有一个数，就是i对应的nums[i];另一种情况就是不止一个数就是i-1最小的子数组乘积f[i-1]乘i位置对应的nums[i]，但是这里的nums[i]可能是小于0,所以这里还得分两种情况：一个是nums[i]>0,那么就是最小的子数组乘积g[i-1]乘i位置对应的nums[i]；如果nums[i]<0,就是最大的子数组乘积g[i-1]乘i位置对应的nums[i]。然后取这两种情况的最小值。
- 初始化 第一位置的值可能也会取到，那么就多开一个空间，把f[0]位置和g[0]初始化为1，从而不影响后面的最大乘积。这里同时也要注意下标的映射关系，多开了一个空间,那么对应nums[i]的位置就得向前挪一个。
- 填表顺序 从左往右 两个表一起填
- 返回值 f表里面的最大值
3.2 代码
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
vector<int> f(n+1),g(n+1);
f[0]=g[0]=1;
int ret=INT_MIN;
for(int i=1;i<=n;i++)
{
int x=nums[i-1],y=f[i-1]*nums[i-1],z=g[i-1]*nums[i-1];
f[i]=max(x,max(y,z));
g[i]=min(x,min(y,z));
ret=max(ret,f[i]);
}
return ret;
}
};4. 1567. 乘积为正数的最长子数组长度
4.1 分析
一、题目解析： 求数组乘积为正数的最长长度，可能会有所有元素和和子数组所有的和比较，然后取最大的一个。但是可能会存在i位置小于0，所以的多加一个数组。 二、算法原理：
- 状态表示 以i位置为结尾，所有子数组乘积为正数的最长长度。 f[i]：表示以i位置为结尾所有字数组中乘积为正数的最长长度 g[i]：表示以i位置为结尾所有字数组中乘积为负数的最长长度
- 状态转移方程 那么f[i]就可能分两种情况：一种就是只有一个数，就是i对应的nums[i]，如果num[i]<0，长度就为0，num[i]>0，长度就为1; 另一种情况就是不止一个数就是i-1最大的子数组乘积为正数的最长长度,如果num[i]>0，长度就为就是以i-1为结尾的子数组乘积为正数的最长长度再加1；num[i]<0，长度就为就是以i-1为结尾的子数组乘积为负数的最长长度再加1，但是如果前面g[i-1]的结果为0，那么结果就是0，所以得先判断g[i-1]是否等于0。
再把这两种情况优化一下，当num[i]>0，那么如果只有num[i]结果就是1，也就是没有不止一个元素的时候大，所以，直接用f[i-1]+1就行。 num[i]<0，先判断判断g[i-1]是否等于0，是就是0，不是就取g[i-1]+1。 f的状态转移方程：
那么g[i]就可能分两种情况：一种就是只有一个数，就是i对应的nums[i]，如果num[i]<0，长度就为1，num[i]>0，长度就为0; 另一种情况就是不止一个数就是i-1最大的子数组乘积为负数的最长长度,如果num[i]>0，长度就为就是以i-1为结尾的子数组乘积为负数的最长长度再加1，也不能直接加一，先判断判断g[i-1]是否等于0，是就是0，不是就取g[i-1]+1； num[i]<0，长度就为就是以i-1为结尾的子数组乘积为正数的最长长度再加1。
g的状态转移方程：
- 初始化 第一位置的值可能也会取到，那么就多开一个空间，把f[0]位置初始化为0，g[0]初始化,0，从而不影响后面的结果。这里同时也要注意下标的映射关系，多开了一个空间,那么对应nums[i]的位置就得向前挪一个。
- 填表顺序 从左往右 两个表一起填
- 返回值 返回f表里面最大值
4.2 代码
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
vector<int> f(n+1),g(n+1);
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;
}
};有问题请指出，大家有一起进步！！！