Тот факт, что это может быть любой путь, и тот факт, что существуют отрицательные числа, все это усложняет. В противном случае это была бы простая рекурсия.
Но здесь все еще есть рекурсия.
Учитывая поддерево, которое имеет только один уровень, например:
A
B C
Тогда у вас есть 6 возможностей A * B * C, или A * B, или A * C, или A, или B, или C.
Учитывая более большое дерево, вот так:
A
X Y
где X и Y сами по себе являются деревьями, тогда учтите, что у вас есть 6 возможных комбинаций:
A
A * (любой потенциальный продукт из X, включающий корневой узел X) * (любой потенциальный продукт из Y, включающий корневой узел Y)
A * (любой потенциальный продукт из X, который включает корневой узел X)
A * (любой потенциальный продукт из Y, который включает корневой узел Y)
Любой потенциальный продукт от X
Любой потенциальный продукт от Y
Любой из этих продуктов может оказаться самым крупным.
Так что теперь вы можете написать рекурсивную функцию, которая включает в себя эти 6 возможностей, и вызвать функцию, начиная с корневого узла. В функции вы рассчитаете все 6 из этих продуктов (рекурсивно вызывая вашу функцию), и если какой-либо из этих продуктов будет больше глобального максимума, у вас будет новый глобальный максимум.