Integer Break

Sizga n butun soni berilgan. Uni kamida ikkita musbat butun sonlarga bo'ling va ularning ko'paytmasini maksimal qiling.

Maksimal ko'paytmani qaytaring.

Cheklov: 2 ≤ n ≤ 58. Masalan, n = 10 uchun eng yaxshi bo'linish 3 + 3 + 4, ko'paytma 36.

func solve(n int) int {
    // ...
}

Misollar

Input: n = 10
Output: 36
Tushuntirish: 10 = 3 + 3 + 4, ko'paytma = 3 * 3 * 4 = 36.

Input: n = 2
Output: 1

Input: n = 3
Output: 2

Maslahatlar

1. Har bir sonni "birinchi bo'lak + qolgan qismning eng yaxshi ko'paytmasi" ko'rinishida ifodalab, kichikroq sonlar uchun javoblarni saqlab boruvchi dinamik dasturlash (DP) haqida o'ylab ko'ring.
2. dp[1..3] uchun boshlang'ich qiymatlarni to'g'ridan-to'g'ri belgilang; keyin har bir i=4..n uchun barcha j=1..i-1 bo'linishlarini sinab, j * dp[i-j] ning eng kattasini dp[i] sifatida saqlang (bu yerda dp[i-j] o'zi ham qolgan qismni yana bo'lish natijasi bo'lishi mumkin).