Find Contiguous Subarray with Largest Min Plus Max π -- Not OA but an INTERVIEW Question! π· :)
Learn this problem
GoogleINTERNOAProblem statement
Given an array of n positive integers, find a contiguous subarray
(containing more than one number) with the largest min + max.
Function
findContiguousSubarrayWithLargestMinPlusMax(nums: int[]) β int
Complete the function findContiguousSubarrayWithLargestMinPlusMax in the editor.
findContiguousSubarrayWithLargestMinPlusMax has the following parameter:
int nums[n]: an array of integers
Returns
int: the largest sum of min and max of a contiguous subarray
Note
Solve better than O(n^3)
π‘ π«§A HUGE THANK YOU TO THE INCREDIBLE RACHEL!π π§‘
Examples
Example 1
nums = [4, 6, 2, 8, 10]return = 18The contiguous subarray with the largest min + max is [8, 10], where the min is 8 and the max is 10. Therefore, the answer is 10 + 8 = 18.
Example 2
nums = [6, 2, 9, 1, 7]return = 11The contiguous subarray with the largest min + max is [2, 9], where the min is 2 and the max is 9. Therefore, the answer is 2 + 9 = 11.
Constraints
2 <= nums.length <= 10^51 <= nums[i] <= 10^9