Mündəricat
Problem bəyanat
Tam ədədin fasiləsi LeetCode Həlli – Tam ədəd verilir n, cəminə bölün k müsbət tam ədədlər, Harada k >= 2, və həmin tam ədədlərin hasilini maksimuma çatdırın.
Geri dönməliyik əldə edə biləcəyimiz maksimum məhsul.
Input: n = 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1.
Izahat
8-in maksimum hasilini tapmaq üçün 8-i iki şərtin cəminə bölün (artıqlığın qarşısını almaq üçün birinci həddi ikincidən kiçik və ya ona bərabər saxlayın):
1 + 7 --> 1 * 7 = 7
2 + 6 --> 2 * 6 = 12
3 + 5 --> 3 * 5 = 15
4 + 4 --> 4 * 4 = 16
Buradan belə görünür ki, maksimum məhsul 16-dır, lakin biz iki terminin hər birini daha çox terminə bölmək və bütün bunları yoxlamaqdan çəkinmişik. Gəlin 6-nı 3 + 3-ə bölək:
2 + 6 = 2 + 3 + 3 --> 2 * 3 * 3 = 18
doğru cavabla nəticələnir. Ancaq bunu əldə etməyin başqa bir yolu 6 olduğunu bildiyimiz 9-nın əvvəllər hesablanmış maksimum məhsulunu təkrar istifadə etməkdir:
2 * (3 * 3) = 2 * max_product_of_6 = 2 * 9 = 18
Beləliklə, i <= j və i + j = n ilə i və j-nin hər seçimi üçün yoxlayın i * j lakin DA i və j üçün əvvəllər hesablanmış maksimum məhsulların i və j-dən böyük olub olmadığını yoxlayın. n = 1 ilə başlayın və son n-ə qədər qurun. Əvvəllər hesablanmış dəyərləri dp massivində saxlayın.
Kodu
Tam Ədədi Fasilə LeetCode Həlli üçün Java Kodu
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for(int i = 2; i <= n; i ++) {
for(int j = 1; j < i; j ++) {
dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
}
}
return dp[n];
}
}
Tam Ədədi Fasilə LeetCode Həlli üçün C++ Kodu
class Solution {
public:
int integerBreak(int n) {
if (n <= 2)
return 1;
vector<int> maxArr(n+1, 0);
maxArr[1] = 0;
maxArr[2] = 1; // 2=1+1 so maxArr[2] = 1*1
for (int i=3; i<=n; i++) {
for (int j=1; j<i; j++) {
maxArr[i] = max(maxArr[i], max(j*(i-j), j*maxArr[i-j]));
}
}
return maxArr[n];
}
};
Tam Ayı Fasilə LeetCode Həlli üçün Python Kodu
class Solution(object):
def integerBreak(self, n):
dp = [None, 1]
for m in range (2, n + 1):
j = m - 1
i = 1
max_product = 0
while i <= j:
max_product = max(max_product, max(i, dp[i]) * max(j, dp[j]))
j -= 1
i += 1
dp.append(max_product)
return dp[n]
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
Hər bir “i” üçün 1-dən “i”yə qədər hesablayırıq, buna görə də zaman mürəkkəbliyi O(n^2) olur.
Kosmik Mürəkkəblik
Bir dp istifadə edirik massiv ölçüsü n beləliklə fəzanın mürəkkəbliyi O(n) olacaq
