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](/predownloaded/17/3d/173d93e3ff19495104d5b1280b4af767478527c1.png)
↵
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](/predownloaded/17/3d/173d93e3ff19495104d5b1280b4af767478527c1.png)
