Best Time to Buy and Sell Stock

Let’s solve the actual game, not the fake “pick a nice subsequence” version. The order of moves matters, but the whole thing collapses once you look at one target answer.

Threshold graph

Fix a number $g$. We ask:

Can Alex force the final beauty to be at least $g$?

Create a graph $G_g$ with one vertex per array index. For every pair $i<j$, add an edge $(i,j)$ if

$a_j-a_i \ge g.$

If Alex locks both endpoints of any edge, the final beauty is at least $g$. If he never locks both endpoints of an edge, the final beauty is less than $g$.

So this is a vertex-claiming game:

• Hao removes vertices.
• Alex locks vertices.
• Alex wants to fully claim an edge.
• Hao wants Alex’s locked set to be independent.

Important: this is not absolute difference. The pair direction is index order. For $i<j$, the value is $a_j-a_i$. Turning this into $|a_i-a_j|$ is how you send your solution into the wall.

The key mini-game

First solve the version where Alex moves first on some graph.

If some vertex has degree at least $2$, Alex wins immediately:

1. Alex locks that vertex $v$.
2. Hao can remove at most one neighbor of $v$.
3. At least one other neighbor remains.
4. Alex locks that neighbor and completes an edge.

If every vertex has degree at most $1$, then the graph is just a matching plus isolated vertices. Hao wins by a simple response strategy: whenever Alex locks one endpoint of an unmatched edge, Hao removes its partner. If Alex locks an isolated vertex, Hao removes anything. Alex never gets both endpoints of an edge.

Therefore, in an Alex-first game:

$\text{Alex wins} \iff \Delta(G_g) \ge 2.$

Back to the real game

In the real game, Hao moves first. Suppose Hao removes vertex $p$. Then Alex is first on the remaining graph $G_g-p$.

From the mini-game above:

• If $G_g-p$ has maximum degree at most $1$, Hao can keep the beauty below $g$.
• If $G_g-p$ has some degree at least $2$, Alex can force beauty at least $g$.

So Alex can force beauty at least $g$ iff there is no vertex $p$ whose deletion makes all remaining degrees at most $1$.

That gives a monotone predicate, so we binary search the largest winning $g$.

Which first deletions can matter?

Let $deg[i]$ be the degree of vertex $i$ in $G_g$, but we only care about values $0,1,2,>2$.

If all degrees are at most $1$, Alex already loses the threshold game, so check(g)=false.

If some vertex has degree greater than $2`, Hao has only one possible way to fix it: delete that vertex itself. Deleting one neighbor would reduce its degree by only$1$, leaving degree at least$2$.

If the maximum degree is exactly $2$, pick any vertex $v$ with degree $2$. A successful first deletion must be either:

• $v$ itself, or
• one of the two neighbors of $v$.

Otherwise $v$ still has degree $2$ after the deletion, and Alex wins.

So for each $g$, we only test at most three candidate first moves by recomputing the capped degrees after deleting that candidate.

Computing capped degrees in linear time

Naively, $G_g$ has $O(n^2)$ edges. We obviously do not build that unless we enjoy TLE as a lifestyle.

For a fixed right endpoint $i$, dangerous left endpoints $j<i$ satisfy:

$a_i-a_j \ge g,$

or equivalently:

$a_j \le a_i-g.$

We only need to know whether there are $0$, $1$, $2$, or at least $3$ such endpoints. If there are at least three, the three smallest previous values will all work. If there are fewer than three, all working values are among the three smallest previous values anyway.

So scan left to right while maintaining the three smallest previous values. This counts dangerous partners to the left.

Similarly, for a fixed left endpoint $i`, dangerous right endpoints$j>i$ satisfy:

$a_j-a_i \ge g,$

or:

$a_j \ge a_i+g.$

Scan right to left while maintaining the three largest future values. This counts dangerous partners to the right.

Cap every count at $3$. Exact degree is unnecessary; distinguishing $2$ from $>2$ is enough.

Each degree computation is $O(n)$ because the maintained lists have size at most three. Each check(g) recomputes this a constant number of times, so it is $O(n)$. Binary search gives:

$O(n\log 10^9)$

per total input size, which is fine for $\sum n \le 10^5$.

Why the binary search works

If Alex can force beauty at least $g$, then he can also force beauty at least any smaller value. Smaller $g$ only adds more edges to the threshold graph, never removes them.

So check(g) is monotone: true, true, true, then false, false, false as $g$ increases. The answer is the largest true $g$.

Also, yes, the answer can be negative. The stock market got hands.