❔ Задача с LeetCode «Burst Balloons №312»

Вам дано n шариков с индексом от 0 до n - 1. На каждом шарике нанесен номер, представленный массивом nums. Вам нужно лопнуть все шарики.

Если вы лопнете i-й шарик, то получите nums[i - 1] * nums[i] * nums[i + 1] монет. Если значение i - 1 или i + 1 выходит за пределы массива, то считайте, что это воздушный шар с нарисованной на нем цифрой 1.

Верните максимальное количество монет, которые вы сможете собрать, разумно лопнув воздушные шары.

Пример №1:
Входные данные: nums = [3,1,5,8]
Вывод: 167
Пояснение:
nums = [3,1,5,8] —> [3,5,8] —> [3,8] —> [8] —> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

Пример №2:
Входные данные: nums = [1,5]
Вывод: 10

Ограничения:
1. n == nums.length
2. 1 <= n <= 300
3. 0 <= nums[i] <= 100

📱 Java Developer | #задача #hard