Burst Balloons

📝 Vazifa tavsifi

Sizga n ta sharning ustiga yozilgan raqamlar nums massivi berilgan. Siz barcha sharlarni portlatishingiz kerak.

Agar siz i indeksdagi sharni portlatsangiz, u holda nums[i - 1] * nums[i] * nums[i + 1] miqdorda tanga olasiz. Agarda i - 1 yoki i + 1 massiv chegarasidan tashqariga chiqib ketsa, ularning o'rniga 1 raqami bor deb hisoblashingiz mumkin.

Barcha sharlarni portlatib yig'ish mumkin bo'lgan maksimal tangalar (coins) miqdorini qaytaring.

Misol:

Input: nums = [3,1,5,8]
Output: 167
Tushuntirish:
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