Build the longest spike from an array

A spike is a sequence of integers that strictly increases up to a single peak and then strictly decreases. The peak belongs to both parts, and either part may be empty, so a single number is a spike of length 1.

For example, [1, 6, 9, 4] is a spike. [3, 3, 8, 2] is not, because the rising part repeats 3. [2, 9, 9, 1] is not, because the peak is not unique.

You are given an integer array arr of length n. You may choose any subset of its elements (each element used at most once) and arrange them in any order.

Implement longest_spike(arr: List[int]) -> int, which returns the maximum length of a spike you can build. Return 0 for an empty array.

Constraints

• 0 <= n <= 10^5
• -10^9 <= arr[i] <= 10^9
• Aim for O(n) or O(n log n).

Example 1

arr = [2, 5, 3, 2, 8, 3, 3]
output: 6

One answer is [2, 3, 5, 8, 3, 2]. Only one 5 exists, so it goes on one side. One of the three 3s cannot be used.

Example 2

arr = [7, 7, 1, 1]
output: 3

The best spike is [1, 7, 1]. A second 7 cannot be placed anywhere.

Be ready for follow-ups: return the spike itself, require both sides to be non-empty, fix the peak value, or solve it without reordering (keep the original order).

Reconstructed from the reported question; details may differ from what interviewers ask.