在Python中查找数字的最大复合被加数数

假设我们有一个给定的数 N，它在 (1<=N<=10^9) 范围内，我们必须将 N 表示为最大可能数量的复合被加数的总和并返回这个最大数，否则当我们找不到任何拆分，然后返回-1。

因此，如果输入像 16，那么输出将是 4，因为 16 可以写为 4 + 4 + 4 + 4 或 8 + 8，但是 (4 + 4 + 4 + 4) 具有最大被加数。

在线示例

让我们看看以下实现以获得更好的理解 -

global max_val
max_val = 16
def pre_calc():
   table = [-1 for i in range(max_val)]
   table[0] = 0
   v = [4, 6, 9]
   for i in range(1, max_val, 1):
      for k in range(3):
         j = v[k]
         if (i >= j and table[i - j] != -1):
            table[i] = max(table[i], table[i - j] + 1)
   return table
def max_summ(table, n):
   if (n < max_val):
      return table[n]
   else:
      t = int((n - max_val) / 4)+ 1
      return t + table[n - 4 * t]
n = 16
table = pre_calc()
print(max_summ(table, n))

输入

16

4