陕西省西安市网站建设公司,wordpress没小工具,分销网站建立,微网站建设申请1.最大子数组和 力扣 给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。 示例 1#xff1a; 输入#xff1a;nums [-2,1,-3,4,-1,2,1,-5…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]
输出23class Solution {const int INF0x3f3f3f3f;
public:int maxSubArray(vectorint nums) {int nnums.size();vectorint dp(n1);int ret-INF;for(int i1;in;i){dp[i]max(nums[i-1],dp[i-1]nums[i-1]);retmax(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] 都可以得到最大和 3class Solution {const int INF 0x3f3f3f3f;
public:int maxSubarraySumCircular(vectorint nums){int n nums.size();int sum 0;for (auto sh : nums) sum sh;vectorint f(n 1);//找最大值vectorint 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-retmin0)return retmax;return retmax retmin ? retmax : max(retmax, sum - retmin);*/return retmax retmin ? retmax : max(retmax, sum - retmin0?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(vectorint nums){int nnums.size();vectorint f(n1);auto gf;int retINT_MIN;int retminINT_MAX;f[0]g[0]1;for(int i1;in;i){f[i]max(nums[i-1],max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));retmax(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]));retminmin(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(vectorint nums) {int nnums.size();vectorint f(n1);auto gf;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;}
};
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]
输出0class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {int nnums.size();int dp[2]{0};int sum0;for(int i2;in;i){dp[i%2]nums[i]-nums[i-1]nums[i-1]-nums[i-2]?dp[(i-1)%2]1:0;sumdp[i%2];}return sum;}
};
6.最长湍流子数组 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 给定一个整数数组 arr 返回 arr 的 最大湍流子数组的长度 。 如果比较符号在子数组中的每个相邻元素对之间翻转则该子数组是 湍流子数组 。 更正式地来说当 arr 的子数组 A[i], A[i1], ..., A[j] 满足仅满足下列条件时我们称其为湍流子数组 若 i k j 当 k 为奇数时 A[k] A[k1]且当 k 为偶数时A[k] A[k1]或 若 i k j 当 k 为偶数时A[k] A[k1] 且当 k 为奇数时 A[k] A[k1]。 示例 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]
输出1class Solution {
public:int maxTurbulenceSize(vectorint arr) {int narr.size();vectorint f(n,1);auto gf;int ret1;for(int i1;in;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;}retmax(ret,max(g[i],f[i]));}return ret;}
};
