✅ Number of Subarrays with Bounded Maximum| W/Explanation | Linear time,Logic+Maths
Consider following test case: \n\n\n\t\t[3,4,1,2,1,3]\n\t\tleft=3\n\t\tright=5\n Here, we can see that any element which is between left & right are always incl
Consider following test case: \n\n\n\t\t[3,4,1,2,1,3]\n\t\tleft=3\n\t\tright=5\n* Here, we can see that any element which is between `left` & `right` are always included for counting in the answer without watching which element is maximum.\n* Now we can also notice that if any element which is less than `left` occurs than it will affect the successive elements which are also less than `left`. Here the element is `1 & 2 & then 1`. Thus `[1],[1,2],[1,2,1],[2],[2,1],[1]` are `subtracted` from the answer. This count is nothing but `(z*(z+1))/2` where `z` is number of consecutive elements less than left (In this case z=3 therefore count=6).\n\n\n\nNow Follow the steps for coding part:\n1.Increase the count of variable **tp** till we encounter an element which is greater than `right`. The moment we encounter it, update the value of **tp** to 0 and add `(tp*(tp+1))/2` to the **ans**.\n2.If we encounter an element which is less than `left` than we have to iterate through the next indices until we get an element>=`left` count such iteration as **z**. Now we have to subtrat the `(z*(z+1))/2 `elements as they will not have any maximum element between `left` & `right`.\n\n```\nTime Complexity: O(N)\nSpace Complexity: O(1),excluding the Input array\n```\n\n```\nint numSubarrayBoundedMax(vector<int>& nums, int left, int right) {\n        int n=nums.size();\n        int ans=0;\n        int tp=0;\n        for(int i=0;i<n;i++){\n            if(nums[i]>=left&&nums[i]<=right) tp++;\n            else if(nums[i]>right){\n                ans+=(tp*(tp+1))/2;\n                tp=0;\n                \n            }\n            else{\n                int z=1;\n                tp++;\n                while(i+1<n && nums[i+1]<left){\n                    z++;\n                    tp++;\n                    i++;\n                }\n                ans-=(z*(z+1))/2;\n            }\n        }\n        if(tp>0)ans+=(tp*(tp+1))/2;\n        return ans;\n}\n```\n
['Math', 'C']