21. Лопаем шарики#

📝 Условие#

Лопая шарик i, получаете nums[left]·nums[i]·nums[right]. В каком порядке лопать, чтобы набрать максимум?

Совет

На LeetCode main не нужен: данные приходят аргументами метода класса Solution.
Формат ниже — для запуска у себя через cin / cout.

📥 Входные данные#

В первой строке число n (1 ≤ n ≤ 300). Во второй — n чисел nums[i] (0 ≤ nums[i] ≤ 100).

📤 Выходные данные#

Одно число — максимальное количество монет.

🧪 Тесты#

Тест 1#

Ввод:

4
3 1 5 8

Вывод:

167

Тест 2#

Ввод:

2
1 5

Вывод:

10

Тест 3#

Ввод:

1
7

Вывод:

7

Заметка

Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.

💡 Подсказка#

⬅️ К списку задач уровня