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!