购物网站底部设计,vi设计英文,做网站上海的备案地址,微站开发个人主页 #xff1a; 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 分析
一、… 个人主页 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(vectorint nums) {int nnums.size();vectorint dp(n1);dp[0]0;int retINT_MIN;for(int i1;in;i){dp[i]max(nums[i-1],dp[i-1]nums[i-1]);retmax(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表中可能会存在全是负数序列的情况这里就得加一个判断如果sumgmin那么就返回fmax不然就比较两类和的大小返回大的那一个。
2.2 代码
class Solution {
public:int maxSubarraySumCircular(vectorint nums) {int n nums.size();vectorint f(n1),g(n1);int fmaxINT_MIN,sum0,gminINT_MAX;for(int i1;in;i){f[i]max(nums[i-1],f[i-1]nums[i-1]);fmaxmax(fmax,f[i]);g[i]min(nums[i-1],g[i-1]nums[i-1]);gminmin(gmin,g[i]);sumnums[i-1];}return sumgmin?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(vectorint nums) {int n nums.size();vectorint f(n1),g(n1);f[0]g[0]1;int retINT_MIN;for(int i1;in;i){int xnums[i-1],yf[i-1]*nums[i-1],zg[i-1]*nums[i-1];f[i]max(x,max(y,z));g[i]min(x,min(y,z));retmax(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长度就为0num[i]0长度就为1; 另一种情况就是不止一个数就是i-1最大的子数组乘积为正数的最长长度,如果num[i]0长度就为就是以i-1为结尾的子数组乘积为正数的最长长度再加1num[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长度就为1num[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]位置初始化为0g[0]初始化,0从而不影响后面的结果。这里同时也要注意下标的映射关系多开了一个空间,那么对应nums[i]的位置就得向前挪一个。 填表顺序 从左往右 两个表一起填 返回值 返回f表里面最大值
4.2 代码
class Solution {
public:int getMaxLen(vectorint nums) {int n nums.size();vectorint f(n1),g(n1);int retINT_MIN;for(int i1;in;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;}retmax(ret,f[i]);}return ret;}
};有问题请指出大家有一起进步
