Question $7)$ You are given a string representing a binary tree where each node is either $\text{'}0\text{'}$ or $\text{'}1\text{'}.$ The

root of the tree is at index $0.$ Write a dynamic programming algorithm to find the maximum path sum

in the binary tree, where a path is defined as any sequence of nodes from some starting node to any

node in the tree along the parent$-$child connections. Note that the path can start and end at any node

in the tree. $(10$ points$)$

Hint: In Min Heap, we saw how to represent a tree using an array $($a string in this question$).$

Examples:

max$\_$path$\_$sum$("1010010")$ # Output: $3$

$($as the maximum path sum is obtained by the path: $1($root$)->1->1($leaf$))$

Other paths have a smaller sum value.