Maximize min+max of contiguous subarray

Q: Maximize min+max of contiguous subarray

This question evaluates understanding of array algorithms and competency in identifying and reasoning about minimum and maximum values within contiguous subarrays, emphasizing extremal value handling.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an array of n positive integers nums.

Find a contiguous subarray that contains at least two elements and maximizes the value:

(minimum element of the subarray) + (maximum element of the subarray)

Return this maximum possible sum.

If multiple subarrays yield the same maximum sum, you only need to return the value of that sum (not the subarray itself).

You may assume n ≥ 2.

Example

Input:

nums = [5, 12, 9, 6, 4]

All valid subarrays of length ≥ 2 and their (min + max) values include:

[5, 12] → min = 5, max = 12, sum = 17
[5, 12, 9] → min = 5, max = 12, sum = 17
[12, 9] → min = 9, max = 12, sum = 21
[12, 9, 6] → min = 6, max = 12, sum = 18
[9, 6] → min = 6, max = 9, sum = 15
...

The maximum possible value of min + max is 21, from subarray [12, 9].

Output:

Maximize min+max of contiguous subarray

Overview

Comments (0)