Why does the non-adjacent sum problem have optimal substructure?

Question

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?

Answer 1

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.