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?