# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n**(Also explained in the code)**\n\n#### ***Approach 1 (Binary Search)***\n1. The `maximumScore` function is the main function that calculates the maximum score. It takes a vector of integers `nums` and an integer `k` as input.\n\n1. Inside the `maximumScore` function, it first calculates the maximum score using the `solve` function and stores it in the variable `ans`.\n\n1. Then, it reverses the `nums` vector using the `reverse` function. This is done to calculate the maximum score from the other side of the array.\n\n1. Finally, it returns the maximum of the two scores calculated in step 2 and step 3, which effectively returns the overall maximum score.\n\n1. The `solve` function takes two parameters: the `nums` vector and an integer `k`, which represents a pivot point in the vector.\n\n1. It calculates the maximum score starting from the pivot point `k` and moving both left and right in the `nums` vector.\n\n1. The `left` vector is used to store the minimum values found when moving from left to right, starting from the pivot point `k`.\n\n1. The `currMin` variable is initialized with `INT_MAX` to track the minimum value. It is updated while iterating through the vector to find the minimum values.\n\n1. The `for` loop moves from the pivot point `k` towards the beginning of the vector (i.e., from right to left), and it updates the `left` vector with the minimum values encountered.\n\n1. Similarly, the `right` vector is used to store the minimum values found when moving from right to left, starting from the pivot point `k`.\n\n1. Again, the `currMin` variable is initialized with `INT_MAX` to track the minimum value and is updated while iterating through the vector.\n\n1. The second `for` loop moves from the pivot point `k` towards the end of the vector, and it updates the `right` vector with the minimum values encountered.\n\n1. The `ans` variable is used to store the maximum score. It is calculated using a nested for loop that iterates through the `right` vector.\n\n1. For each element in the `right` vector, it calculates the index at which the corresponding minimum value is found in the `left` vector. This is done using the `lower_bound` function.\n\n1. It calculates the size of the subarray by subtracting the index from step 14 from the sum of k and the current iteration variable `j`.\n\n1. The maximum score for the current element is calculated as the product of the minimum value from the `right` vector and the size of the subarray.\n\n1. The maximum score is updated if the calculated score is greater than the current maximum.\n\n1. Finally, the function returns the maximum score calculated.\n\n# Complexity\n- *Time complexity:*\n $$O(nlogn)$$\n \n\n- *Space complexity:*\n $$O(n)$$\n \n\n\n# Code\n```C++ []\n\nclass Solution {\npublic:\n int maximumScore(vector& nums, int k) {\n int ans = solve(nums, k);\n reverse(nums.begin(), nums.end());\n return max(ans, solve(nums, nums.size() - k - 1));\n }\n \n int solve(vector& nums, int k) {\n int n = nums.size();\n vector left(k, 0);\n int currMin = INT_MAX;\n for (int i = k - 1; i >= 0; i--) {\n currMin = min(currMin, nums[i]);\n left[i] = currMin;\n }\n \n vector right;\n currMin = INT_MAX;\n for (int i = k; i < n; i++) {\n currMin = min(currMin, nums[i]);\n right.push_back(currMin);\n }\n \n int ans = 0;\n for (int j = 0; j < right.size(); j++) {\n currMin = right[j];\n int i = lower_bound(left.begin(), left.end(), currMin) - left.begin();\n int size = (k + j) - i + 1;\n ans = max(ans, currMin * size);\n }\n \n return ans;\n }\n};\n\n```\n```C []\n\n#include \n#include \n\nint min(int a, int b) {\n return a < b ? a : b;\n}\n\nint max(int a, int b) {\n return a > b ? a : b;\n}\n\nint lower_bound(int arr[], int size, int value) {\n int left = 0, right = size;\n while (left < right) {\n int mid = left + (right - left) / 2;\n if (arr[mid] < value) {\n left = mid + 1;\n } else {\n right = mid;\n }\n }\n return left;\n}\n\nint solve(int nums[], int size, int k) {\n int *left = (int *)malloc(k * sizeof(int));\n int currMin = INT_MAX;\n for (int i = k - 1; i >= 0; i--) {\n currMin = min(currMin, nums[i]);\n left[i] = currMin;\n }\n\n int *right = (int *)malloc((size - k) * sizeof(int));\n currMin = INT_MAX;\n int rightSize = 0;\n for (int i = k; i < size; i++) {\n currMin = min(currMin, nums[i]);\n right[rightSize] = currMin;\n rightSize++;\n }\n\n int ans = 0;\n for (int j = 0; j < rightSize; j++) {\n currMin = right[j];\n int i = lower_bound(left, k, currMin);\n int size = (k + j) - i + 1;\n ans = max(ans, currMin * size);\n }\n\n free(left);\n free(right);\n return ans;\n}\n\nint maximumScore(int nums[], int size, int k) {\n int ans = solve(nums, size, k);\n int *reversedNums = (int *)malloc(size * sizeof(int));\n for (int i = 0; i < size; i++) {\n reversedNums[i] = nums[size - 1 - i];\n }\n int reversedAns = solve(reversedNums, size, size - k - 1);\n free(reversedNums);\n return max(ans, reversedAns);\n}\n\nint main() {\n int nums[] = {1, 4, 3, 7, 4, 5};\n int size = sizeof(nums) / sizeof(nums[0]);\n int k = 3;\n int result = maximumScore(nums, size, k);\n printf("Maximum Score: %d\\n", result);\n return 0;\n}\n\n\n```\n\n```Java []\nclass Solution {\n public int maximumScore(int[] nums, int k) {\n int ans = solve(nums, k);\n for (int i = 0; i < nums.length / 2; i++) {\n int temp = nums[i];\n nums[i] = nums[nums.length - i - 1];\n nums[nums.length - i - 1] = temp;\n }\n \n return Math.max(ans, solve(nums, nums.length - k - 1));\n }\n \n public int solve(int[] nums, int k) {\n int n = nums.length;\n int left[] = new int[k];\n int currMin = Integer.MAX_VALUE;\n for (int i = k - 1; i >= 0; i--) {\n currMin = Math.min(currMin, nums[i]);\n left[i] = currMin;\n }\n \n List right = new ArrayList();\n currMin = Integer.MAX_VALUE;\n for (int i = k; i < n; i++) {\n currMin = Math.min(currMin, nums[i]);\n right.add(currMin);\n }\n \n int ans = 0;\n for (int j = 0; j < right.size(); j++) {\n currMin = right.get(j);\n int i = binarySearch(left, currMin);\n int size = (k + j) - i + 1;\n ans = Math.max(ans, currMin * size);\n }\n\n return ans;\n }\n \n public int binarySearch(int[] nums, int num) {\n int left = 0;\n int right = nums.length;\n \n while (left < right) {\n int mid = (left + right) / 2;\n if (nums[mid] < num) {\n left = mid + 1;\n } else {\n right = mid;\n }\n }\n \n return left;\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def maximumScore(self, nums: List[int], k: int) -> int:\n def solve(nums, k):\n n = len(nums)\n left = [0] * k\n curr_min = inf\n for i in range(k - 1, -1, -1):\n curr_min = min(curr_min, nums[i])\n left[i] = curr_min\n\n right = []\n curr_min = inf\n for i in range(k, n):\n curr_min = min(curr_min, nums[i])\n right.append(curr_min)\n\n ans = 0\n for j in range(len(right)):\n curr_min = right[j]\n i = bisect_left(left, curr_min)\n size = (k + j) - i + 1\n ans = max(ans, curr_min * size)\n \n return ans\n \n return max(solve(nums, k), solve(nums[::-1], len(nums) - k - 1))\n\n```\n\n```javascript []\nfunction maximumScore(nums, k) {\n const ans = solve(nums, k);\n const reversedNums = [...nums].reverse();\n return Math.max(ans, solve(reversedNums, nums.length - k - 1));\n}\n\nfunction solve(nums, k) {\n const n = nums.length;\n const left = new Array(k).fill(0);\n let currMin = Infinity;\n\n for (let i = k - 1; i >= 0; i--) {\n currMin = Math.min(currMin, nums[i]);\n left[i] = currMin;\n }\n\n const right = [];\n currMin = Infinity;\n\n for (let i = k; i < n; i++) {\n currMin = Math.min(currMin, nums[i]);\n right.push(currMin);\n }\n\n let ans = 0;\n\n for (let j = 0; j < right.length; j++) {\n currMin = right[j];\n const i = lowerBound(left, currMin);\n const size = (k + j) - i + 1;\n ans = Math.max(ans, currMin * size);\n }\n\n return ans;\n}\n\nfunction lowerBound(arr, value) {\n let left = 0;\n let right = arr.length;\n\n while (left < right) {\n const mid = left + Math.floor((right - left) / 2);\n\n if (arr[mid] < value) {\n left = mid + 1;\n } else {\n right = mid;\n }\n }\n\n return left;\n}\n\nconst nums = [1, 4, 3, 7, 4, 5];\nconst k = 3;\nconst result = maximumScore(nums, k);\nconsole.log("Maximum Score: " + result);\n\n```\n\n---\n\n#### ***Approach 2 (Monotonic Stack)***\n- This code aims to find the maximum score for a specific element `nums[k]` in an array `nums` by considering elements to its left and right.\n\n- The variable `n` stores the length of the `nums` array.\n\n- The code initializes two arrays, `left` and `right`, with default values of -1 and `n`, respectively. These arrays will be used to store the left and right boundaries for each element in the `nums` array.\n\n- A stack named `stack` is used to help calculate the boundaries of elements as we traverse the array.\n\n- The first loop, moving backward from the end of the array to the beginning, calculates the left boundaries for each element and updates the `left` array. It does this by comparing the current element with the elements in the stack. If the current element is smaller than the element at the top of the stack, the stack element\'s left boundary is set to the current index. This continues until the current element is greater than the element at the top of the stack.\n\n- The second loop, moving forward from the beginning of the array to the end, calculates the right boundaries for each element and updates the `right` array in a similar way to the first loop.\n\n- After calculating the left and right boundaries for each element, the code proceeds to calculate the maximum score. It initializes `ans` to 0 to store the maximum score found so far.\n\n- It then iterates through the `nums` array. For each element at index `i`, it checks if the left boundary (`left[i]`) is less than `k` and the right boundary (`right[i]`) is greater than `k`. This indicates that the element `nums[i]` can be included in the calculation of the maximum score. If these conditions are met, the code calculates the score as `nums[i] * (right[i] - left[i] - 1)`. The `-1` is used to exclude the element `nums[i]` from the scoring calculation.\n\n- For each element, if the calculated score is greater than the current maximum score (ans), it updates `ans` with the newly calculated score.\n\n- Finally, the code returns `ans` as the maximum score for the element at index `k`.\n\n# Complexity\n- *Time complexity:*\n $$O(n)$$\n \n\n- *Space complexity:*\n $$O(n)$$\n \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n int maximumScore(vector& nums, int k) {\n int n = nums.size();\n vector left(n, -1);\n vector stack;\n \n for (int i = n - 1; i >= 0; i--) {\n while (!stack.empty() && nums[stack.back()] > nums[i]) {\n left[stack.back()] = i;\n stack.pop_back();\n }\n \n stack.push_back(i);\n }\n \n vector right(n, n);\n stack.clear();\n for (int i = 0; i < n; i++) {\n while (!stack.empty() && nums[stack.back()] > nums[i]) {\n right[stack.back()] = i;\n stack.pop_back();\n }\n \n stack.push_back(i);\n }\n \n int ans = 0;\n for (int i = 0; i < n; i++) {\n if (left[i] < k && right[i] > k) {\n ans = max(ans, nums[i] * (right[i] - left[i] - 1));\n }\n }\n \n return ans;\n }\n};\n\n\n```\n```C []\n\nclass Solution {\npublic:\n int maximumScore(vector& nums, int k) {\n int n = nums.size();\n vector left(n, -1);\n vector stack;\n\n // Calculate left boundaries for each element.\n for (int i = n - 1; i >= 0; i--) {\n while (!stack.empty() && nums[stack.back()] > nums[i]) {\n left[stack.back()] = i;\n stack.pop_back();\n }\n\n stack.push_back(i);\n }\n\n vector right(n, n);\n stack.clear();\n\n // Calculate right boundaries for each element.\n for (int i = 0; i < n; i++) {\n while (!stack.empty() && nums[stack.back()] > nums[i]) {\n right[stack.back()] = i;\n stack.pop_back();\n }\n\n stack.push_back(i);\n }\n\n int ans = 0;\n\n // Calculate the maximum score for each element.\n for (int i = 0; i < n; i++) {\n if (left[i] < k && right[i] > k) {\n ans = max(ans, nums[i] * (right[i] - left[i] - 1));\n }\n }\n\n return ans;\n }\n};\n\n\n```\n\n```Java []\nclass Solution {\n public int maximumScore(int[] nums, int k) {\n int n = nums.length;\n int left[] = new int[n];\n Arrays.fill(left, -1);\n Stack stack = new Stack<>();\n \n for (int i = n - 1; i >= 0; i--) {\n while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {\n left[stack.pop()] = i;\n }\n \n stack.push(i);\n }\n \n int right[] = new int[n];\n Arrays.fill(right, n);\n stack = new Stack<>();\n \n for (int i = 0; i < n; i++) {\n while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {\n right[stack.pop()] = i;\n }\n \n stack.push(i);\n }\n \n int ans = 0;\n for (int i = 0; i < n; i++) {\n if (left[i] < k && right[i] > k) {\n ans = Math.max(ans, nums[i] * (right[i] - left[i] - 1));\n }\n }\n \n return ans;\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def maximumScore(self, nums: List[int], k: int) -> int:\n n = len(nums)\n left = [-1] * n\n stack = []\n \n for i in range(n - 1, -1, -1):\n while stack and nums[stack[-1]] > nums[i]:\n left[stack.pop()] = i\n \n stack.append(i)\n \n right = [n] * n\n stack = []\n for i in range(n):\n while stack and nums[stack[-1]] > nums[i]:\n right[stack.pop()] = i\n \n stack.append(i)\n\n ans = 0\n for i in range(n):\n if left[i] < k and right[i] > k:\n ans = max(ans, nums[i] * (right[i] - left[i] - 1))\n \n return ans\n\n```\n\n```javascript []\nclass Solution {\n maximumScore(nums, k) {\n const n = nums.length;\n const left = new Array(n).fill(-1);\n const stack = [];\n\n // Calculate left boundaries for each element.\n for (let i = n - 1; i >= 0; i--) {\n while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {\n left[stack[stack.length - 1]] = i;\n stack.pop();\n }\n\n stack.push(i);\n }\n\n const right = new Array(n).fill(n);\n stack.length = 0;\n\n // Calculate right boundaries for each element.\n for (let i = 0; i < n; i++) {\n while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {\n right[stack[stack.length - 1]] = i;\n stack.pop();\n }\n\n stack.push(i);\n }\n\n let ans = 0;\n\n // Calculate the maximum score for each element.\n for (let i = 0; i < n; i++) {\n if (left[i] < k && right[i] > k) {\n ans = Math.max(ans, nums[i] * (right[i] - left[i] - 1));\n }\n }\n\n return ans;\n }\n}\n\n```\n\n---\n#### ***Approach 3 (Greedy)***\n- This code aims to find the maximum score for a specific element `nums[k]` in an array `nums` by considering elements to its left and right.\n\n- The variable `n` stores the length of the `nums` array.\n\n- The variables `left` and `right` are initialized with the value of `k`. These variables will be used to keep track of the current left and right boundaries, respectively. `ans` is initialized with the value of `nums[k]`, which represents the initial maximum score.\n\n- The variable `currMin` is also initialized with the value of `nums[k]`. This variable will keep track of the minimum value of the elements within the current range.\n\n- The code enters a `while` loop, and the loop continues as long as either the left or right boundary can be expanded.\n\n- Inside the loop, the code checks which direction to expand. It compares the elements at the left and right boundaries. If the element to the left (`nums[left - 1]`) is smaller or doesn\'t exist (when `left` reaches the beginning of the array), it means it\'s preferable to expand to the right. Otherwise, if the right element (`nums[right + 1]`) is smaller or doesn\'t exist (when `right` reaches the end of the array), the code expands to the left.\n\n- When the code expands the boundaries, it updates `left` or `right` accordingly and also updates `currMin` to the minimum value within the current range.\n\n- In each iteration, the code calculates the score for the current range by multiplying `currMin` by the width of the range (`right - left + 1`). This represents the score of including `nums[k]` along with the elements within the range.\n\n- The calculated score is compared to the current maximum score (`ans`), and if it is greater, the maximum score is updated with the newly calculated score.\n\n- The loop continues to expand the boundaries and calculate the score as long as it\'s possible to do so. It effectively finds the maximum score for `nums[k]` by considering different combinations of left and right boundaries.\n\n- Finally, the code returns `ans` as the maximum score for the element at index `k`.\n\n# Complexity\n- *Time complexity:*\n $$O(n)$$\n \n\n- *Space complexity:*\n $$O(1)$$\n \n\n\n# Code\n```C++ []\n\nclass Solution {\npublic:\n int maximumScore(vector& nums, int k) {\n int n = nums.size();\n int left = k;\n int right = k;\n int ans = nums[k];\n int currMin = nums[k];\n \n while (left > 0 || right < n - 1) {\n if ((left > 0 ? nums[left - 1]: 0) < (right < n - 1 ? nums[right + 1] : 0)) {\n right++;\n currMin = min(currMin, nums[right]);\n } else {\n left--;\n currMin = min(currMin, nums[left]);\n }\n \n ans = max(ans, currMin * (right - left + 1));\n }\n \n return ans;\n }\n};\n\n```\n```C []\n#include \n\nint maximumScore(int nums[], int n, int k) {\n int left = k;\n int right = k;\n int ans = nums[k];\n int currMin = nums[k];\n \n while (left > 0 || right < n - 1) {\n if ((left > 0 ? nums[left - 1] : 0) < (right < n - 1 ? nums[right + 1] : 0)) {\n right++;\n currMin = (currMin < nums[right]) ? currMin : nums[right];\n } else {\n left--;\n currMin = (currMin < nums[left]) ? currMin : nums[left];\n }\n \n int score = currMin * (right - left + 1);\n ans = (ans > score) ? ans : score;\n }\n \n return ans;\n}\n\nint main() {\n int nums[] = {1, 4, 3, 7, 4, 5};\n int n = sizeof(nums) / sizeof(nums[0]);\n int k = 3;\n int result = maximumScore(nums, n, k);\n printf("Maximum Score: %d\\n", result);\n return 0;\n}\n\n\n\n```\n\n```Java []\nclass Solution {\n public int maximumScore(int[] nums, int k) {\n int n = nums.length;\n int left = k;\n int right = k;\n int ans = nums[k];\n int currMin = nums[k];\n \n while (left > 0 || right < n - 1) {\n if ((left > 0 ? nums[left - 1]: 0) < (right < n - 1 ? nums[right + 1] : 0)) {\n right++;\n currMin = Math.min(currMin, nums[right]);\n } else {\n left--;\n currMin = Math.min(currMin, nums[left]);\n }\n \n ans = Math.max(ans, currMin * (right - left + 1));\n }\n \n return ans;\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def maximumScore(self, nums: List[int], k: int) -> int:\n n = len(nums)\n left = k\n right = k\n ans = nums[k]\n curr_min = nums[k]\n \n while left > 0 or right < n - 1:\n if (nums[left - 1] if left else 0) < (nums[right + 1] if right < n - 1 else 0):\n right += 1\n curr_min = min(curr_min, nums[right])\n else:\n left -= 1\n curr_min = min(curr_min, nums[left])\n\n ans = max(ans, curr_min * (right - left + 1))\n \n return ans\n\n```\n\n```javascript []\nfunction maximumScore(nums, k) {\n const n = nums.length;\n let left = k;\n let right = k;\n let ans = nums[k];\n let currMin = nums[k];\n \n while (left > 0 || right < n - 1) {\n if ((left > 0 ? nums[left - 1] : 0) < (right < n - 1 ? nums[right + 1] : 0)) {\n right++;\n currMin = Math.min(currMin, nums[right]);\n } else {\n left--;\n currMin = Math.min(currMin, nums[left]);\n }\n \n const score = currMin * (right - left + 1);\n ans = Math.max(ans, score);\n }\n \n return ans;\n}\n\nconst nums = [1, 4, 3, 7, 4, 5];\nconst k = 3;\nconst result = maximumScore(nums, k);\nconsole.log("Maximum Score:", result);\n\n```\n\n---\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---

Maximum Score of a Good Subarray

Problem Description

Problem Description

Answer Panel