Find max min-plus-max over all subarrays

You are given an array `arr` of `n` integers. A **subarray** is a contiguous non-empty segment of the array. For any subarray `arr[l..r]` (0-indexed), define: \[ X(l, r) = \min(arr[l..r]) + \max(arr[l..r]) \] Your task is to compute the maximum possible value of `X(l, r)` over all subarrays of `arr`. ### Input - An integer `n` (the length of the array). - An array `arr` of `n` integers (can be positive, zero, or negative). ### Output - A single integer: the maximum value of `min(subarray) + max(subarray)` over all possible non-empty contiguous subarrays. ### Requirements - Describe an efficient algorithm and its time and space complexity. - Aim for better than \(O(n^2)\) time for large `n` (e.g., `n` up to around `2 * 10^5`).