Java | O(N^2) to O(N) optimization | Intuition
Bruteforce solution is straightforward, we consider every possibility (all subarrays), maintain a maximum and as long as there is  valid maximum within range we
Bruteforce solution is straightforward, we consider every possibility (all subarrays), maintain a maximum and as long as there is  valid maximum within range we increment the count. But this results in **O(n<sup>2</sup>)**\n\nObservations:\n\t1. \tOnce we encounter an element, *j* which is greater than the maximum range, we don\'t need to consider further any more subarrays for element at *i* (we are reseting our count).\n\t2. \tIf we encounter an element *j* which is within the range, it contributes equal to the length of valid subarray so far + 1 (+1 for it\'s count as an individual element).\n\t3. \tIf we counter an element *j* which is less the minimum range, it contributes equal amount to the length of valid subarray - the length of elments that are smaller than the minimum range. For e.g., in an array of [2,2,1,1] for left = 2 and right = 3, \nwe will have counts like \n```\n[1, \n(1(previous value) + 1(length) + 1(individual)) = 3, \n3(previous value) + 2(valid length) + 0(individual) = 5, \n5(previous value) + 2(valid length = distance till last maximum value) + 0(individual) = 7] = 7.\n```\n\nHere goes the implementation,\n\n**O(n<sup>2</sup>)**  **[TLE]**\n```\nclass Solution {\n    public int numSubarrayBoundedMax(int[] nums, int left, int right) {\n        int count = 0;\n        \n        for(int i=0; i<nums.length; i++) {\n            int max = 0;\n            for(int j=i; j<nums.length; j++) {\n                max = Math.max(max, nums[j]);\n                if(max <= right && max >= left) {\n                    count++;\n                }\n            }\n        }\n        \n        return count;\n    }\n}\n```\n\n**O(n)**\n```\nclass Solution {\n    public int numSubarrayBoundedMax(int[] nums, int left, int right) {       \n        int res = 0, start = 0, end = 0, curr = 0, lastGoodIndex = -1;\n        for(int i=0; i<nums.length; i++) {\n            if(nums[i] >= left && nums[i] <= right) {\n                curr += end - start + 1;\n                lastGoodIndex = i;\n                end++;\n            }else if(nums[i] < left) {\n                if(lastGoodIndex != -1) {\n                    curr += ((end - start) - (i - 1 - lastGoodIndex));\n                }\n                end++;\n            }else{\n                start = i+1;\n                end = i+1;\n                res += curr;\n                curr = 0;\n                lastGoodIndex = -1;\n            }            \n        }\n        \n        res += curr;\n        \n        return res;\n    }\n}\n```
['Array', 'Dynamic Programming', 'Java']