You are given an integer array nums.
Return the length of the longest semi-decreasing subarray of nums, and 0 if there are no such subarrays.
Example 1:
Input: nums = [7,6,5,4,3,2,1,6,10,11] Output: 8 Explanation: Take the subarray [7,6,5,4,3,2,1,6]. The first element is 7 and the last one is 6 so the condition is met. Hence, the answer would be the length of the subarray or 8. It can be shown that there aren't any subarrays with the given condition with a length greater than 8.
Example 2:
Input: nums = [57,55,50,60,61,58,63,59,64,60,63] Output: 6 Explanation: Take the subarray [61,58,63,59,64,60]. The first element is 61 and the last one is 60 so the condition is met. Hence, the answer would be the length of the subarray or 6. It can be shown that there aren't any subarrays with the given condition with a length greater than 6.
Example 3:
Input: nums = [1,2,3,4] Output: 0 Explanation: Since there are no semi-decreasing subarrays in the given array, the answer is 0.
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109The problem is essentially finding the maximum length of the inverse pairs. We can use a hash table d to record the index i corresponding to each number x in the array.
Next, we traverse the keys of the hash table in descending order of the numbers. We maintain a number k to keep track of the smallest index that has appeared so far. For the current number x, we can get a maximum inverse pair length of d[x][|d[x]|-1]-k + 1, where |d[x]| represents the length of the array d[x], i.e., the number of times the number x appears in the original array. We update the answer accordingly. Then, we update k to d[x][0], which is the index where the number x first appears in the original array. We continue to traverse the keys of the hash table until all keys are traversed.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
Java
C++
Go
TypeScript
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 605,143 views views
Watch 9 more video solutions →Practice Maximum Length of Semi-Decreasing Subarrays with our built-in code editor and test cases.
Practice on FleetCode