Best Window Extremes

Bronze

10000ms500MB

Given an array of positive integers, find a contiguous subarray containing at least two numbers with the largest min + max.

Formally, given an array nums, find indices l and r (where r >= l + 1) that maximize min(nums[l..r]) + max(nums[l..r]). Return that maximum value.

Examples

Example 1

Input: nums = [4, 9, 1, 1]
Output: 13
Explanation: min + max of subarray [4, 9] = 4 + 9 = 13

Example 2

Input: nums = [1, 2, 3, 1]
Output: 5
Explanation: min + max of subarray [2, 3] = 2 + 3 = 5

Constraints

$2 \leq$ nums.length $\leq 10^5$
$1 \leq$ nums[i] $\leq 10^6$

Examples

Example 1

Input

nums = [4, 9, 1, 1]

Output

Example 2

Input

nums = [1, 2, 3, 1]

Output

Example 3

Input

nums = [72, 95, 58, 61]

Output

167

Loading editor...

Click "Run" to test with sample cases or "Submit" to run all tests.

Best Window Extremes

Bronze

10000ms500MB

Given an array of positive integers, find a contiguous subarray containing at least two numbers with the largest min + max.

Formally, given an array nums, find indices l and r (where r >= l + 1) that maximize min(nums[l..r]) + max(nums[l..r]). Return that maximum value.

Examples

Example 1

Input: nums = [4, 9, 1, 1]
Output: 13
Explanation: min + max of subarray [4, 9] = 4 + 9 = 13

Example 2

Input: nums = [1, 2, 3, 1]
Output: 5
Explanation: min + max of subarray [2, 3] = 2 + 3 = 5

Constraints

$2 \leq$ nums.length $\leq 10^5$
$1 \leq$ nums[i] $\leq 10^6$

Examples

Example 1

Input

nums = [4, 9, 1, 1]

Output

Example 2

Input

nums = [1, 2, 3, 1]

Output

Example 3

Input

nums = [72, 95, 58, 61]

Output

167

Loading editor...

Click "Run" to test with sample cases or "Submit" to run all tests.