Build the longest spike from an array

A spike is any sequence that rises strictly to one peak and then falls strictly. The peak counts in both parts. A one-element sequence is a spike: the peak alone.

Because we may pick any subset and reorder it, the positions in the input do not matter. Only the multiset of values matters. So start by counting how often each value appears.

Brute force. Try every subset, sort it into the best arrangement, and check whether it is a spike. That costs O(2^n * n log n). It is only useful as a test oracle on tiny inputs. Say it out loud, then move on.

Key observation. Look at what a spike can hold:

• The peak must be strictly larger than every other element. Two copies of the largest value cannot both fit: wherever the second copy goes, it sits on a side that must be strictly below the peak. So the largest chosen value appears exactly once.
• Every other value v can appear at most twice: once on the rising side and once on the falling side. A third copy would sit next to a copy of itself on one side.

Greedy is optimal. Use the global maximum M as the peak, once. For every other distinct value v, take min(count[v], 2) copies. Put one copy of each value on the left in increasing order, and the second copies (where they exist) on the right in decreasing order. Both sides are strictly monotone because each side holds each value once. Every value is below M, so the peak is strictly the largest.

Why the global maximum: choosing a smaller peak p throws away every value above p and lets p itself appear only once instead of twice. That can never beat the greedy count, which is an upper bound by the two observations above.

So the answer is 1 + sum(min(count[v], 2) for v != M).

Invariant for the construction. The left side is the sorted list of distinct values below M. The right side is the sorted list of values below M with count at least 2, reversed. Each side has no repeats, so each side is strictly monotone.

from collections import Counter
from bisect import bisect_left
from itertools import combinations, permutations
from typing import List


def longest_spike(arr: List[int]) -> int:
    """Max length of a spike built from a sub-multiset of arr. O(n)."""
    if not arr:
        return 0
    counts = Counter(arr)
    peak = max(counts)
    return 1 + sum(min(c, 2) for v, c in counts.items() if v != peak)


def build_spike(arr: List[int]) -> List[int]:
    """Return one longest spike. O(n log n) for the sort."""
    if not arr:
        return []
    counts = Counter(arr)
    peak = max(counts)
    below = sorted(v for v in counts if v != peak)
    left = below
    right = [v for v in reversed(below) if counts[v] >= 2]
    return left + [peak] + right


def is_spike(seq: List[int]) -> bool:
    if not seq:
        return False
    top = seq.index(max(seq))
    rising = all(seq[i] < seq[i + 1] for i in range(top))
    falling = all(seq[i] > seq[i + 1] for i in range(top, len(seq) - 1))
    return rising and falling


def longest_spike_brute(arr: List[int]) -> int:
    """Exponential oracle for tiny inputs."""
    best = 0
    for k in range(1, len(arr) + 1):
        for combo in combinations(arr, k):
            if any(is_spike(list(p)) for p in permutations(combo)):
                best = max(best, k)
    return best


def longest_bitonic_subsequence(arr: List[int]) -> int:
    """Follow-up: no reordering allowed. LIS from both ends, O(n log n)."""
    def lis_ending_at(a: List[int]) -> List[int]:
        tails: List[int] = []
        out: List[int] = []
        for x in a:
            i = bisect_left(tails, x)       # strict increase
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
            out.append(i + 1)
        return out

    if not arr:
        return 0
    inc = lis_ending_at(arr)
    dec = lis_ending_at(arr[::-1])[::-1]
    return max(i + d - 1 for i, d in zip(inc, dec))


if __name__ == "__main__":
    import random

    assert longest_spike([]) == 0
    assert longest_spike([9]) == 1
    assert longest_spike([4, 4, 4]) == 1
    assert longest_spike([2, 5, 3, 2, 8, 3, 3]) == 6
    assert build_spike([2, 5, 3, 2, 8, 3, 3]) == [2, 3, 5, 8, 3, 2]
    assert longest_spike([1, 2, 3, 4]) == 4
    assert longest_spike([7, 7, 1, 1]) == 3
    assert longest_spike([-3, -3, 0, -1]) == 4

    for _ in range(300):
        arr = [random.randint(-2, 3) for _ in range(random.randint(1, 6))]
        n = longest_spike(arr)
        assert n == longest_spike_brute(arr), arr
        s = build_spike(arr)
        assert len(s) == n and is_spike(s), (arr, s)
        assert not Counter(s) - Counter(arr)

    assert longest_bitonic_subsequence([1, 11, 2, 10, 4, 5, 2, 1]) == 6
    assert longest_bitonic_subsequence([5, 4, 3]) == 3
    print("all tests passed")

• longest_spike: O(n) time to count, O(d) space for d distinct values.
• build_spike: O(n + d log d) time for the sort of distinct values, O(d) space.
• longest_bitonic_subsequence (follow-up): O(n log n) time, O(n) space.
• The brute force oracle is O(2^n * n! * n) and is only for tests.

• [] → 0 (no elements, no spike).
• [9] → 1 (the peak alone).
• [4, 4, 4] → 1 (the maximum can be used only once, and nothing is below it).
• [2, 5, 3, 2, 8, 3, 3] → 6, for example [2, 3, 5, 8, 3, 2]. The third 3 is dropped, and 5 appears once.
• [1, 2, 3, 4] → 4 ([1, 2, 3, 4]; the falling side may be empty).
• [7, 7, 1, 1] → 3 ([1, 7, 1]; only one 7 fits).
• [-3, -3, 0, -1] → 4 ([-3, -1, 0, -3]; negatives work the same way).
• Large input, n = 10^5 all equal → 1, in linear time.

1. Return the spike, not just its length. Use build_spike: sorted distinct values below the peak, then the peak, then the values with count at least 2 in reverse order.
2. The peak must be a given value p. Ignore every value above p. The answer is 1 + sum(min(count[v], 2) for v < p), or 0 if p is not in the array.
3. Both sides must be non-empty (a true mountain, length at least 3). Take the greedy spike. If its right side is empty (no value below the peak has two copies), move the smallest value from the left side to the right side. That keeps both sides strictly monotone and the length unchanged, but it needs at least two distinct values below the peak. If that fails, no mountain exists and the answer is 0 (for example [7, 7] or [1, 7]).
4. No reordering: pick a subsequence in the original order. This is the longest bitonic subsequence. Compute the strict LIS length ending at each index from the left and from the right with patience sorting, then take max(inc[i] + dec[i] - 1). See longest_bitonic_subsequence. If the elements must be contiguous, it becomes the longest mountain subarray, a single linear scan.
5. Streaming updates: add and remove values, query the answer after each. Keep count[v] and a running sum S = sum(min(count[v], 2)), updated in O(1) per change. Keep the current maximum in a sorted container (or a max-heap with lazy deletion). The answer is S - min(count[M], 2) + 1. Each update costs O(log d).

Mid-level (L4)

• Sees that reordering makes positions irrelevant and moves to value counts.
• States the two limits: the peak once, every other value at most twice.
• Writes the O(n) count, handles the empty array and the all-equal case.

Senior (L5)

• Argues why the greedy is optimal (upper bound plus a matching construction) instead of only asserting it.
• Builds the actual spike and checks it with a validator or a brute-force oracle on small inputs.
• Handles the "both sides non-empty" variant and the fixed-peak variant quickly.

Staff (L6+)

• Recognizes the no-reorder variant as longest bitonic subsequence and gives the O(n log n) LIS-based solution, with strict versus non-strict handled correctly (bisect_left).
• Designs the streaming version with clear update and query costs.
• Discusses input clarifications up front: whether a single element counts, duplicates, negative values, and the expected size of n.