# algorithms – Proving existence of an optimal substructure for the DP problem “Sherlock and Cost” from HackerRank

Problem statement from HackerRank ( source: https://www.hackerrank.com/challenges/sherlock-and-cost/problem ) :

In this challenge, you will be given an array $$B$$ and must determine an array $$A$$ . There is a special rule: For all $$i$$, $$A(i) leq B(i)$$ , . That is, $$A(i)$$ can be any number you choose such that $$1 leq A(i) leq B(i)$$ . Your task is to select a series of $$A(i)$$ given $$B(i)$$ such that the sum of the absolute difference of consecutive pairs of $$A$$ is maximized. This will be the array’s cost, and will be represented by the variable $$S$$ below.
The equation can be written: $$S = sum_{i=2}^{N}{ ( A(i) – A(i-1) )}$$
For example, if the array $$B = (1,2,3)$$ , we know that $$1 leq A(1) leq 1$$ , $$1 leq A(2) leq 2$$ , and $$1 leq A(3) leq 3$$ . Arrays meeting those guidelines are:
(1,1,1), (1,1,2), (1,1,3)
(1,2,1), (1,2,2), (1,2,3)
Our calculations for the arrays are as follows:
|1-1| + |1-1| = 0 , |1-1| + |2-1| = 1, |1-1| + |3-1| = 2
|2-1| + |1-2| = 2 ,|2-1| + |2-2| = 1 ,|2-1| + |3-2| = 2
The maximum value obtained is 2.

My attempt for proving the existence of an optimal substructure:
Denote $$SEQ$$ as the set of all sequences $$A$$ s.t. $$forall 1 leq i leq n$$, $$1 leq A(i) leq B(i)$$. For all $$A in SEQ$$ define $$S_A = sum_{i=2}^{n}{ ( A(i) – A(i-1) )}$$ .

Let $$hat{A} in SEQ$$ s.t. for every $$hat{A’} in SEQ$$, $$S_hat{A’} leq S_hat{A}$$.
Thus, there exist a sequence of optimal choices $$langle o_1,o_2,…,o_n rangle$$ s.t. for all $$1 leq i leq n$$ we chose $$1 leq alpha leq B(i)$$ s.t. $$alpha in B$$ and we define $$hat{A}(i) = alpha$$, and this is the $$o_i$$ choice.
Looking at the sequence of choices $$langle o_1,o_2,…,o_{n-1} rangle$$ and looking at the sequence $$tilde A$$ that derives from these choices, $$tilde A$$ must be optimal. Otherwise, there exist a sequence of choices $$< o_1,…,o_l >$$ s.t. $$l < n-1$$ and note that the sequence of choices $$< o_1,…,o_l, o_n >$$ give $$hat{A}$$. Notice that we have $$l+1$$ choices in the sequence $$< o_1,…,o_l >$$ and notice that $$langle o_1,o_2,…,o_n rangle$$ is an optimal sequence of choices, but $$l+1 < n$$ and since every sequence of choices that yields $$hat{A}$$ must have at-least $$n$$ choices, this means $$n leq l+1 < n$$ , a contradiction.

What do you think about this attempt? how would you prove the existence of an optimal substructure?

Thanks in advance for any help!