C ++中有界最大值的子数组数
为了解决这个问题,我们将遵循以下步骤-
ret:=0,dp:=0,上一页:=-1
对于范围从0到A–1的i
如果A[i]<L且i>0,则ret:=ret+dp
如果A[i]>R,则prev:=i和dp:=0
否则,当A[i]>=L且A[i]<=R时,则dp:=i–prev和ret:=ret+dp
返回ret
范例(C++)
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class Solution { public: int numSubarrayBoundedMax(vector<int>& A, int L, int R) { int ret = 0; int dp = 0; int prev = -1; for(int i = 0; i < A.size(); i++){ if(A[i] < L && i > 0){ ret += dp; } if(A[i] > R){ prev = i; dp = 0; } else if(A[i] >= L && A[i] <= R){ dp = i - prev; ret += dp; } } return ret; } }; main(){ vector<int> v = {2,1,4,3}; Solution ob; cout << (ob.numSubarrayBoundedMax(v, 2, 3)); }
输入值
[2,1,4,3] 2 3
输出结果
3