Proving existence of an optimal substructure for the DP problem "Sherlock and Cost" from HackerRank

Question

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!

Answer 1

Your attempt sounds specious since your proof does not use any specific property of the objective function, $ S = \sum_{i=2}^{n}| A[i] - A[i-1]| $. Had your proof been correct, there would have been an optimal substructure for any arbitrary objective function we could have defined for $A$, which does not make sense.

---

To prove the existence of an optimal substructure, we had better state what is the optimal structure of the subproblems of the given problem. To accomplish that, we have to state

• what are the overlapping subproblems and
• how to obtain the optimal solution of a larger subproblem by using optimal solutions to smaller subproblems.

The overlapping subproblems are $P(e, t)$ for $1\le e\le n$ and $1\le t\le B[t]$, the problem of choosing sequence $A[0], A[1], \cdots, A[e]$ such that

• $1\le A[i]\le B[i]$ for all $1\le i\lt e$ and
• $A[e]=t$ and
• that sequence reaches the maximum $S =\sum_{i=2}^{e}| A[i] - A[i-1] |$ among all sequences that satisfy the two conditions above.

Since the order of summation does not matter, we know that the following optimal substructure.

• if $A[1], A[2], \cdots, A[e+1]$ for $1\le e\le n-1$ is a solution to $P(e+1, A[e+1])$ , then $A[1], A[2], \cdots, A[e]$ must be a solution to $P(e, A[e])$.
• Given $1\le t'\le B[e+1]$ where $1\le e\le n-1$, we can consider sequences $A[1], A[2], \cdots, t, t'$ for all $t$ with $1\le t\le B[e], $ where $A[1], A[2], \cdots, A[e]$ is a solution to $P(e, t)$. The sequence with the maximum $S =\sum_{i=2}^{e+1}| A[i] - A[i-1] |$ among them will be a solution to $P(e+1, t')$.
• The solution to the original problem is the sequence with the maximum $S =\sum_{i=2}^{n} | A[i] - A[i-1] |$ among solutions to $P(n, t)$ where $1\le t\le B[n]$.

Note that in the explanation here, finding the sequence with the maximum value is the goal instead of just finding the maximum value. There is not much difference in the explanation had the maximum value been used as the goal.

---

The collection of overlapping subproblems is not necessarily unique. There could be many choices of them.

In fact, there is a simpler set of overlapping subproblems, which leads to the simple solution in Python below. Can you find it?

---

The indices start at 1 in the explanation above. They start at 0 in the program below.

def cost(B):
    max1 = 0    # choose 1
    maxB = 0    # choose B[i]
    for i in range(1, n):
        new_max1 = max(max1, maxB + B[i-1] - 1)
        maxB = max(max1 + B[i] - 1, maxB + abs(B[i]- B[i-1]))
        max1 = new_max1
    return max(max1, maxB)