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

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?

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.