Parenthesis Sequence

Sequences like:

• ()()()
• (())((()))()
• (()(()))

A valid parenthesis sequence S[0..2N] has following property:

For every prefix S[0..=i], the number of ( in it is floor(i/2) + 1.

Most Valuable Parentheses

Given a positive integer sequence A[0..2N], construct a valid parenthesis sequence S that maximizes the score. The score is defined as sum(A[i] for i in 0..2N if S[i] == '(').

When scanning A from left to right, greedily pick the position that has maximum value as (.

let mut heap = BinaryHeap::new(); // max heap
let mut seq = vec![')'; 2 * n];

seq[0] = '(';
let mut cnt = 1;

for i in 1..(2 * n - 1) {
    heap.push((arr[i], i));
    if cnt < i / 2 + 1 {
        let (_, j) = heap.pop().unwrap();
        seq[j] = '(';
        cnt += 1;
    }
}

ABC407E