Submask maximum
Your task
Given n (number of bits) and an array val of length 2n where val[m] is a weight assigned to subset m, for each mask m compute the maximum val[s] over all submasks s of m (s & m == s). Return the array of these per-mask submaximums. Constraints: 1 <= n <= 14. The SOS-style DP generalizes from sum to max in O(n * 2n); naive submask enumeration is O(3**n) and too slow at the top.
Examples
max_over_submasks(n: int, val: list[int]) -> list[int]Example 1
Input
max_over_submasks(2, [4, 1, 7, 2])Output
[4, 4, 7, 7]