文章目錄
- 1、最大子數組和
- 2、環形子數組的最大和
- 3、乘積最大子數組
- 4、乘積為正數的最長子數組長度
- 5、 等差數列劃分
- 6、最長湍流子數組
1、最大子數組和
給你一個整數數組 nums ，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
子數組 是數組中的一個連續部分。
class Solution {
public:int maxSubArray(vector<int>& nums) {int size=nums.size();vector<int> dp(size+1);int maxi=-0X3F3F3F3F;for(int i=1;i<=size;i++){dp[i]=max(nums[i-1],dp[i-1]+nums[i-1]);maxi=max(maxi,dp[i]);}return maxi;}
};
2、環形子數組的最大和
給定一個長度為 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 。
class Solution {
public://分為兩種情況考慮int maxSubarraySumCircular(vector<int>& nums) {int n=nums.size();vector<int> d(n+1),p(n+1);int maxi=-0x3F3F3F3F,mini=0x3F3F3F3F,sum=0;for(int i=1;i<=n;i++){ int x=nums[i-1];d[i]=max(x,d[i-1]+x);maxi=max(d[i],maxi);p[i]=min(x,p[i-1]+x);mini=min(mini,p[i]);sum+=x;} return sum==mini?maxi:max((sum-mini),maxi);}
};
3、乘積最大子數組
給你一個整數數組 nums ，請你找出數組中乘積最大的非空連續子數組（該子數組中至少包含一個數字），并返回該子數組所對應的乘積。
測試用例的答案是一個 32-位 整數。
子數組 是數組的連續子序列
class Solution {
public:int maxProduct(vector<int>& nums) {int n=nums.size();//d最大值，p最小值vector<int> d(n+1),p(n+1);d[0]=p[0]=1;int maxi=-0x3F3F3F3F;for(int i=1;i<=n;i++){int x=nums[i-1],a=d[i-1]*nums[i-1],b=p[i-1]*nums[i-1];d[i]=max(x,max(a,b));p[i]=min(x,min(a,b));maxi=max(maxi,d[i]);} return maxi;}
};
4、乘積為正數的最長子數組長度
給你一個整數數組 nums ，請你求出乘積為正數的最長子數組的長度。
一個數組的子數組是由原數組中零個或者更多個連續數字組成的數組。
請你返回乘積為正數的最長子數組長度。
class Solution {
public:int getMaxLen(vector<int>& nums) {int n=nums.size();vector<int> d(n+1),p(n+1);//一個放正數，一個放負數d[0]=p[0]=0;int maxi=-0x3F3F3F3F;for(int i=1;i<=n;i++){if(nums[i-1]>0){d[i]=d[i-1]+1;p[i]=p[i-1]==0?0:p[i-1]+1;}else if(nums[i-1]<0){d[i]=p[i-1]==0?0:p[i-1]+1;p[i]=d[i-1]+1;}maxi=max(maxi,d[i]);}return maxi;}
};
5、 等差數列劃分
如果一個數列 至少有三個元素 ，并且任意兩個相鄰元素之差相同，則稱該數列為等差數列。
例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差數列。
給你一個整數數組 nums ，返回數組 nums 中所有為等差數組的 子數組 個數。
子數組 是數組中的一個連續序列。
class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n=nums.size();vector<int> dp(n);int sum=0;for(int i=2;i<n;i++){dp[i]=nums[i]-nums[i-1]==nums[i-1]-nums[i-2]?dp[i-1]+1:0;sum+=dp[i];}return sum;}
};
6、最長湍流子數組
給定一個整數數組 arr ，返回 arr 的 最大湍流子數組的長度 。
如果比較符號在子數組中的每個相鄰元素對之間翻轉，則該子數組是 湍流子數組 。
更正式地來說，當 arr 的子數組 A[i], A[i+1], …, A[j] 滿足僅滿足下列條件時，我們稱其為湍流子數組：
class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n=arr.size();vector<int> d(n,1),p(n,1);if(n==1)return 1;int maxi=-0x3F3F3F3F;for(int i=1;i<n;i++){if(arr[i-1]<arr[i])d[i]=p[i-1]+1;else if(arr[i-1]>arr[i])p[i]=d[i-1]+1;maxi=max(maxi,max(d[i],p[i]));}return maxi;}
};
