The problem goes like :

We are given an array $$$A$$$ of size $$$N$$$ consisting of positive integers and an integer $$$X$$$. We can perform the following operation atmost once.

• choose any subsequence of $$$A$$$, add $$$X$$$ to each element in that subsequence.

The final motive is to maximise the sum $$$\sum_{i=2}^{N}(A_{i-1} \oplus A_i)$$$.

I don't remember the exact constraints on the values of $$$A_i, \ N \ or X$$$, but I dont' think they matter much. $$$N$$$ is sufficiently large so that the bruteforce exhaustive search won't work. The offical solution uses Dynamic Programming.

I am looking for rigorously justifying that approach. I am unable to prove the two necessary properties for a DP solution namely:

• optimal substructure
• overlapping subproblems

I would highly appreciate someone writing the proof or atleast giving me an outline of the proof.

Attached below is the algorithm written in C++. Link to the image