# 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`). ### Constraints & Assumptions - Preserve the scope, facts, inputs, and requested outputs from the prompt above. - If the prompt leaves a detail unspecified, state a reasonable assumption before relying on it. - Keep the answer interview-ready: concise enough to present, but concrete enough to implement or evaluate. ### Clarifying Questions to Ask - Clarify input sizes, value ranges, mutability, return format, and tie-breaking. - State the target time and space complexity before coding. - Call out edge cases such as empty inputs, duplicates, invalid values, overflow, and boundary sizes. ### What a Strong Answer Covers - A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it. - A correctness argument that explains why the algorithm covers all required cases. - Time and space complexity, plus at least one alternative approach when relevant. - Focused tests for normal cases, edge cases, and failure modes. ### Follow-up Questions - How would the approach change if the input were streaming or too large for memory? - What invariants would you assert in production code? - Which tests would catch off-by-one, duplicate, or tie-breaking bugs?