0
$\begingroup$

In my algorithms class, my professor presented the problem of finding the largest sum of non-adjacent elements in an array. For example, if we have $[1,4,3,8,5]$ the largest sum of non-adjacent elements is $4 + 8 = 12$. My professor said we can solve this problem via dynamic programming since it exhibits optimal substructure.

However, I don't understand why this is true. From what I understand, a problem exhibits optimal substructure if an optimal solution can be found by combining optimal solutions to its subproblems. For example, the problem of finding the shortest path between two vertices $A$ and $C$ in a graph has optimal substructure since if $A\rightarrow B \rightarrow C$ is the shortest path from $A$ to $C$, $A \rightarrow B$ is the shortest path from $A$ to $B$.

Why does this apply to the above subproblem? Consider finding the largest sum of non-adjacent elements in $[1,2,3,4,5]$. The optimal solution is $1 + 3 + 5 = 9$, but the optimal solution to $[1,2,3,4]$ is $2 + 4 = 6$. So the optimal solution to the subproblem of the $4$ element array is not used to construct the optimal solution to the $5$ element array. Is there something I'm missing here?

$\endgroup$

1 Answer 1

1
$\begingroup$

Notice that if in your 5 element array, if the last element is 0 or 1, then the optimal solution will be the optimal solution for your example 4 element array.

My point here is that the largest sum in $A[0,..., n-1]$ will either be $A[n-1]$ plus the largest sum in $A[0,..., n-3]$ (we skip $A[n-2]$ since it is adjacent to $A[n-1]$) or it's the largest sum in $A[0,..., n-2]$ (here we choose to skip $A[n-1] $). As you can see, the solution is dependent on the solutions of two sub-problems. We will choose whichever of the two yields a larger sum.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.