You are given an array of integers nums (0-indexed) and an integer k.
The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A good subarray is a subarray where i <= k <= j.
Return the maximum possible score of a good subarray.
Example 1:
Input: nums = [1,4,3,7,4,5], k = 3 Output: 15 Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.
Example 2:
Input: nums = [5,5,4,5,4,1,1,1], k = 0 Output: 20 Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 2 * 1040 <= k < nums.lengthThis approach involves expanding the subarray to the left and right of index k using two pointers. The objective is to maintain the minimum value in the subarray which can be computed incrementally. Extend the window until further expansion leads to a reduced score.
This Python solution uses two pointers to expand the subarray from the index k. It continuously calculates the score for each valid subarray, updating the maximum score found. The min_val is maintained as the window expands.
C++
Time Complexity: O(n), because each element is processed at most twice, once by each pointer.
Space Complexity: O(1), as we are using only a constant amount of extra space.
This approach involves using a monotonic stack to efficiently determine the range of the smallest element in which it acts as the minimum of a subarray. Thus, it can be used to calculate the potential maximum score by determining the largest possible width for each minimum value.
This Java implementation uses infix traversals and tracks potential boundaries of minimal elements. With left and right arrays, we define valid subarray bounds, ensuring it includes k and updating the max score accordingly.
JavaScript
Time Complexity: O(n), for constructing boundaries with stacks and iterating through the arrays.
Space Complexity: O(n), due to usage of additional arrays and stack.
| Approach | Complexity |
|---|---|
| Sliding Window with Two Pointers | Time Complexity: O(n), because each element is processed at most twice, once by each pointer. |
| Monotonic Stack | Time Complexity: O(n), for constructing boundaries with stacks and iterating through the arrays. |
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 605,139 views views
Watch 9 more video solutions →Practice Maximum Score of a Good Subarray with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor