795. Number of Subarrays with Bounded Maximum

问题：

给定一个数组A，求得连续元素组成子数组最大值在L和R之间的子数组个数。

Example :
Input: 
A = [2, 1, 4, 3]
L = 2
R = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Note:
L, R  and A[i] will be an integer in the range [0, 10^9].
The length of A will be in the range of [1, 50000].

　　

解法：

DP动态规划：每添加一个元素，可得新的子数组数为dp，要求的res+=dp即可。

动态转移方程：

dp[i]=

A[i] > R 的时候：0 （为了计算下面的情况，需要记录当前的 prev = i ）

A[i] < L 的时候：dp[i-1]

L <= A[i] <= R 的时候：要把 这个数 和 之前连续（prev）的所有数 （i-prev）组成新的数组：i-prev

e.g: [1,2]+[3]->[1], [2], [1,2] + [3] ->

[1], [2], [1,2], +

([1,3]由于不连续，所以不能要) [2,3], [1,2,3], [3] 

(i=2,prev=-1,dp=2-(-1)=3)

代码参考：

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        int res=0,dp=0;
        int i=0,prev=-1;
        for(i=0; i<A.size(); i++){
            if(A[i]<L){
                res+=dp;
            }else if(A[i]>R){
                prev=i;
                dp=0;
            }else{
                dp=i-prev;
                res+=dp;
            }
        }
        return res;
    }
};