A number n can be broken into three parts n/2, n/3, and n/4 (consider only the integer part). Each number obtained in this process can be divided further recursively. Find the maximum sum that can be obtained by summing up the divided parts together.
Note: It is possible that we don't divide the number at all.
 
Example 1:
Input:
n = 12
Output: 13
Explanation: Break n = 12 in three parts
{12/2, 12/3, 12/4} = {6, 4, 3}, now current
sum is = (6 + 4 + 3) = 13. Further breaking 6,
4 and 3 into parts will produce sum less than
or equal to 6, 4 and 3 respectively.
Example 2:
Input:
n = 24
Output: 27
Explanation: Break n = 24 in three parts
{24/2, 24/3, 24/4} = {12, 8, 6}, now current
sum is = (12 + 8 + 6) = 26 . But recursively
breaking 12 would produce value 13.
So our maximum sum is 13 + 8 + 6 = 27.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxSum() which accepts an integer n and returns the maximum sum.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
0 <= n <= 10^{6}

Difficulty: EASY
Tags: Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Starter code:
#User function Template for python3



class Solution:

    def maxSum(self, n): 

        # code here 



Solutions:
class Solution:

	def maxSum(self, n):
		if n == 0:
			return 0
		dp = [0 for i in range(n + 1)]
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = max(i, dp[i // 2] + dp[i // 3] + dp[i // 4])
		return dp[n]


class Solution:

	def maxSum(self, n):
		dp = {}

		def backtracking(num):
			if num in dp:
				return dp[num]
			if num == 0:
				return 0
			if num == 1:
				return 0
			maxi = -99999999999
			maxi = max(maxi, num // 2 + num // 3 + num // 4, backtracking(num // 2) + num // 3 + num // 4, backtracking(num // 3) + num // 2 + num // 4, backtracking(num // 4) + num // 2 + num // 3, backtracking(num // 2) + backtracking(num // 3) + num // 4, backtracking(num // 4) + backtracking(num // 3) + num // 2, backtracking(num // 4) + backtracking(num // 2) + num // 3, backtracking(num // 4) + backtracking(num // 2) + backtracking(num // 3))
			dp[num] = maxi
			return maxi
		return backtracking(n)


class Solution:

	def maxSum(self, n):
		dp = []
		for i in range(n + 1):
			dp.append(i)
		for i in range(1, len(dp)):
			dp[i] = max(dp[i // 2] + dp[i // 3] + dp[i // 4], dp[i])
		return dp[-1]


class Solution:

	def maxSum(self, n):
		sum = [0] * (n + 1)

		def divide(n):
			if n <= 1:
				return n
			if sum[n] != 0:
				return sum[n]
			part1 = divide(n // 2)
			part2 = divide(n // 3)
			part3 = divide(n // 4)
			sum[n] = max(n, part1 + part2 + part3)
			return sum[n]
		return divide(n)


class Solution:

	def maxSum(self, n):
		dp = [0 for i in range(n + 1)]
		for i in range(n + 1):
			dp[i] = max(i, dp[i // 2] + dp[i // 3] + dp[i // 4])
		return dp[-1]
		dp = [-1 for i in range(n + 1)]

		def solve(n):
			if n == 0:
				return 0
			if dp[n] != -1:
				return dp[n]
			a1 = max(solve(n // 2), n // 2)
			a2 = max(solve(n // 3), n // 3)
			a3 = max(solve(n // 4), n // 4)
			dp[n] = max(n, a1 + a2 + a3)
			return dp[n]
		ans = solve(n)
		return ans


class Solution:

	def maxSum(self, n):
		dp = [0] * (n + 1)
		if n == 0 or n == 1:
			return 0
		if n <= 4:
			return n
		dp[2] = 2
		dp[3] = 3
		dp[4] = 4
		for i in range(5, n + 1):
			a = max(i // 2, dp[i // 2])
			b = max(i // 3, dp[i // 3])
			c = max(i // 4, dp[i // 4])
			dp[i] = a + b + c
		return dp[-1]


class Solution:

	def maxSum(self, n):
		dp = [-1] * (n + 1)
		return self.func(n, dp)

	def func(self, n, dp):
		if n == 0 or n == 1:
			dp[n] = n
		if dp[n] != -1:
			return dp[n]
		summ = max(n, self.func(n // 2, dp) + self.func(n // 3, dp) + self.func(n // 4, dp))
		return summ


class Solution:

	def find_byRecursion(self, n):
		if n <= 1:
			return 0
		ans1 = self.find_byRecursion(n // 2)
		ans2 = self.find_byRecursion(n // 3)
		ans3 = self.find_byRecursion(n // 4)
		return max(n, ans1 + ans2 + ans3)

	def BottomUp(self, n):
		if n == 0:
			return 0
		memory = [0] * (n + 1)
		memory[0] = 0
		memory[1] = 0
		for i in range(2, n + 1):
			memory[i] = max(i, memory[i // 2] + memory[i // 3] + memory[i // 4])
		return memory[n]

	def maxSum(self, n):
		return self.BottomUp(n)


class Solution:

	def maxSum(self, n):

		def solve(n):
			if n == 0 or n == 1:
				return 0
			a = solve(n // 2)
			b = solve(n // 3)
			c = solve(n // 4)
			return max(n, a + b + c)
		return solve(n)


class Solution:

	def maxSum(self, n):
		summa = n // 2 + n // 3 + n // 4
		if n >= summa:
			return n
		return self.maxSum(n // 2) + self.maxSum(n // 3) + self.maxSum(n // 4)


class Solution:

	def maxSum(self, n):
		if n <= 11:
			return n
		a = [0] * (n + 1)
		for i in range(1, n + 1):
			if i <= 11:
				a[i] = i
			else:
				sum = a[i // 2] + a[i // 3] + a[i // 4]
				a[i] = max(sum, i)
		return a[n]


class Solution:

	def maxSum(self, n):
		if n == 0:
			return 0
		first = n // 2
		second = n // 3
		third = n // 4
		return max(self.maxSum(first) + self.maxSum(second) + self.maxSum(third), n)


class Solution:

	def getMaxSum(self, n, dp):
		result = n // 2 + n // 3 + n // 4
		if dp[n] != -1:
			print('Hello')
			return dp[n]
		if result > n:
			result = self.maxSum(n // 2) + self.maxSum(n // 3) + self.maxSum(n // 4)
		dp[n] = max(n, result)
		return dp[n]

	def maxSum(self, n):
		dp = [-1 for i in range(n + 1)]
		return self.getMaxSum(n, dp)


class Solution:

	def maxSum(self, n):
		dp = [-1] * (n + 1)

		def helper(n):
			if n == 1 or n == 0:
				return n
			if dp[n] != -1:
				return dp[n]
			a = helper(n // 2)
			b = helper(n // 3)
			c = helper(n // 4)
			val = max(a + b + c, n)
			dp[n] = val
			return val
		return helper(n)


class Solution:

	def maxSum(self, n):
		dp = [-1] * (n + 1)
		ans = func(n, dp)
		return ans

def func(n, dp):
	if n == 0:
		return 0
	if dp[n] == -1:
		dp[n] = max(func(n // 2, dp) + func(n // 3, dp) + func(n // 4, dp), n)
	return dp[n]


class Solution:

	def maxSum(self, n):
		if n == 0:
			return 0
		maxx = max(n, self.maxSum(n // 2) + self.maxSum(n // 3) + self.maxSum(n // 4))
		return maxx


class Solution:

	def maxSum(self, n):
		arr = [0]
		for i in range(1, n + 1):
			arr.append(max(arr[i // 2] + arr[i // 3] + arr[i // 4], i))
		return arr[-1]


class Solution:

	def maxSum(self, n):
		if n <= 10:
			return n
		return max(n, self.maxSum(n // 2) + self.maxSum(n // 3) + self.maxSum(n // 4))


class Solution:

	def solve(self, n, hm):
		if n == 0:
			return 0
		if hm.get(n):
			return hm[n]
		a = self.solve(n // 2, hm)
		b = self.solve(n // 3, hm)
		c = self.solve(n // 4, hm)
		hm[n] = max(a, n // 2) + max(b, n // 3) + max(c, n // 4)
		return hm[n]

	def maxSum(self, n):
		hm = {}
		return self.solve(n, hm)


class Solution:

	def maxSum(self, n):
		dp = {}

		def find(n):
			if n == 0:
				return 0
			if n in dp:
				return dp[n]
			a = find(n // 2)
			b = find(n // 3)
			c = find(n // 4)
			dp[n] = max(a + b + c, n)
			return dp[n]
		return find(n)


class Solution:

	def maxSum(self, n):
		dp = [0] * (n + 1)

		def Maximum(n):
			if dp[n] != 0:
				return dp[n]
			if n == 0:
				return 0
			if n > n // 2 + n // 3 + n // 4:
				return n
			dp[n] = Maximum(n // 2) + Maximum(n // 3) + Maximum(n // 4)
			return dp[n]
		Maximum(n)
		return dp[n]


class Solution:

	def maxSum(self, n):
		dp = {}

		def recur(n):
			if n == 0:
				return 0
			if n in dp:
				return dp[n]
			ch1 = recur(n // 2)
			ch2 = recur(n // 3)
			ch3 = recur(n // 4)
			dp[n] = max(n, ch1 + ch2 + ch3)
			return dp[n]
		return recur(n)


class Solution:

	def maxSum(self, n):

		def rec(n):
			if n <= 4:
				return n
			else:
				temp = rec(n // 2) + rec(n // 3) + rec(n // 4)
				return max(temp, n)
		return rec(n)


class Solution:

	def maxSum(self, n):
		if n == 0:
			return 0
		p1 = n // 2
		p2 = n // 3
		p3 = n // 4
		return max(self.maxSum(p1) + self.maxSum(p2) + self.maxSum(p3), n)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.maxSum(n))


class Solution:

	def maxSum(self, n):
		dic = {}
		if n == 0 or n == 1:
			return 0
		if n == 2:
			return 2
		else:
			if n not in dic:
				ans = max(n, self.maxSum(int(n / 4)) + self.maxSum(int(n / 3)) + self.maxSum(int(n / 2)))
			dic[n] = ans
		return dic[n]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.maxSum(n))


class Solution:

	def maxSum(self, n):
		dp = [0] * (n + 1)

		def Maximum(n):
			if dp[n] != 0:
				return dp[n]
			if n == 0:
				return 0
			if n > n // 2 + n // 3 + n // 4:
				return n
			dp[n] = Maximum(n // 2) + Maximum(n // 3) + Maximum(n // 4)
			return dp[n]
		Maximum(n)
		return dp[n]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.maxSum(n))


class Solution:

	def maxSum(self, n):
		if n == 0 or n == 1:
			return 0
		var = 0
		a = self.maxSum(n // 2)
		b = self.maxSum(n // 3)
		c = self.maxSum(n // 4)
		Sum = a + b + c
		var = max(n, Sum)
		return var
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.maxSum(n))


mx = -1

class Solution:

	def maxSum(self, N):
		global mx
		mx = 0

		def solve(n):
			global mx
			if n == 0:
				return 0
			if n > n // 2 + n // 3 + n // 4:
				return n
			res = solve(n // 2) + solve(n // 3) + solve(n // 4)
			return res
		return solve(N)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.maxSum(n))


class Solution:

	def maxSum(self, n1):

		def solve(n):
			if n == 1 or n == 2 or n == 3 or (n == 4) or (n == 5):
				return n
			t1 = n // 2
			t2 = n // 3
			t3 = n // 4
			if t1 + t2 + t3 <= n:
				return n
			return max(t1, solve(t1)) + max(t2, solve(t2)) + max(t3, solve(t3))
		t1 = n1 // 2
		t2 = n1 // 3
		t3 = n1 // 4
		return solve(t1) + solve(t2) + solve(t3)


def rec(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	ans = max(n, rec(n // 2) + rec(n // 4) + rec(n // 3))
	return ans

class Solution:

	def maxSum(self, n):
		res = rec(n // 2) + rec(n // 3) + rec(n // 4)
		return res


import heapq

class Solution:

	def maxSum(self, n):
		hList = []
		heapq.heappush(hList, n * -1)
		sumDic = {}
		tSum = 0
		while len(hList) > 0 and hList[0] * -1 >= 11:
			num = -1 * heapq.heappop(hList)
			if num in sumDic:
				tSum += sumDic[num]
			else:
				a = num // 2
				b = num // 3
				c = num // 4
				if num < a + b + c:
					heapq.heappush(hList, -1 * a)
					heapq.heappush(hList, -1 * b)
					heapq.heappush(hList, -1 * c)
				else:
					tSum += num
		return -1 * sum(hList) + tSum


class Solution:

	def recursion(self, n, dp):
		if n == 0:
			return n
		if dp[n] != -1:
			return dp[n]
		a = self.recursion(n // 2, dp)
		b = self.recursion(n // 3, dp)
		c = self.recursion(n // 4, dp)
		dp[n] = max(n, a + b + c)
		return max(n, a + b + c)

	def maxSum(self, n):
		dp = []
		for i in range(n + n):
			dp.append(-1)
		ans = self.recursion(n, dp)
		return ans


class Solution:

	def recursion(self, n):
		if n == 0:
			return n
		a = self.recursion(n // 2)
		b = self.recursion(n // 3)
		c = self.recursion(n // 4)
		return max(n, a + b + c)

	def maxSum(self, n):
		ans = self.recursion(n)
		return ans


MAX = 1000000

class Solution:

	def maxSum(self, n):
		dp = [0] * (n + 2)
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = max(dp[int(i / 2)] + dp[int(i / 3)] + dp[int(i / 4)], i)
		return dp[n]


class Solution:

	def maxSum(self, n):
		q = []
		q.append(n // 2)
		q.append(n // 3)
		q.append(n // 4)
		ans = sum(q)
		s = ans
		while len(q):
			x = q[0] // 2 + q[0] // 3 + q[0] // 4
			if q[0] < x:
				ans = ans - q[0] + x
				q.append(q[0] // 2)
				q.append(q[0] // 3)
				q.append(q[0] // 4)
				ans
			q.pop(0)
		return ans


class Solution:

	def maxSum(self, n):
		if n <= 1:
			return n
		path1 = self.maxSum(n // 2)
		path2 = self.maxSum(n // 3)
		path3 = self.maxSum(n // 4)
		return max(path1 + path2 + path3, n)


class Solution:

	def maxSum(self, n):
		data = [0 for i in range(n + 1)]
		for i in range(2, n + 1):
			x = 0
			temp = [2, 3, 4]
			for j in temp:
				x = x + max(int(i / j), data[int(i / j)])
			data[i] = x
		return data[n]


class Solution:

	def maxSum(self, n):
		if n == 0 or n == 1:
			return 0
		arr = [0 for i in range(n + 1)]
		arr[2] = 1
		for i in range(3, n + 1):
			a1 = max(int(i // 2), arr[int(i // 2)])
			a2 = max(int(i // 3), arr[int(i // 3)])
			a3 = max(int(i // 4), arr[int(i // 4)])
			arr[i] = a1 + a2 + a3
		return arr[-1]


class Solution:

	def maxSum(self, n):
		if n == 0:
			return 0
		x = self.maxSum(n // 2) + self.maxSum(n // 3) + self.maxSum(n // 4)
		if n <= x:
			return x
		else:
			return n


class Solution:

	def maxSum(self, n):

		def findMax(n, table):
			if table[n] != -1:
				return table[n]
			if n == 0:
				return 0
			n1 = n // 2
			n2 = n // 3
			n3 = n // 4
			res = max(findMax(n1, table) + findMax(n2, table) + findMax(n3, table), n1 + n2 + n3, n)
			table[n] = res
			return res
		table = [-1 for i in range(n + 1)]
		return findMax(n, table)


class Solution:

	def maxSum(self, n):

		def maxsum(n, memo):
			if n not in memo:
				if n <= 9:
					return n
				one = maxsum(n // 2, memo)
				two = maxsum(n // 3, memo)
				three = maxsum(n // 4, memo)
				memo[n] = max(n, one + two + three)
			return memo[n]
		memo = dict()
		return maxsum(n, memo)


class Solution:

	def maxSum(self, n):
		if n == 0 or n == 1:
			return n
		elif n // 2 + n // 3 + n // 4 > n:
			return self.maxSum(n // 2) + self.maxSum(n // 3) + self.maxSum(n // 4)
		else:
			return n


class Solution:

	def solve(self, n, dp):
		if n // 2 + n // 3 + n // 4 <= n:
			return n
		if n in dp.keys():
			return dp[n]
		dp[n] = self.solve(n // 2, dp) + self.solve(n // 3, dp) + self.solve(n // 4, dp)
		return dp[n]

	def maxSum(self, n):
		dp = {}
		return self.solve(n, dp)


class Solution:

	def maxSum(self, n):
		t = [0] * (int(n) + 1)
		for i in range(1, n + 1):
			t[i] = max(i, t[i // 2] + t[i // 3] + t[i // 4])
		return t[n]


class Solution:

	def recur(self, n):
		global dp
		if n == 0:
			return 0
		if dp[n]:
			return dp[n]
		dp[n] = max(n, self.recur(n // 2) + self.recur(n // 3) + self.recur(n // 4))
		return dp[n]

	def maxSum(self, n):
		global dp
		dp = [0] * (n + 1)
		return self.recur(n)


class Solution:

	def maxSum(self, n):
		if n == 0 or n == 1:
			return n
		return max(self.maxSum(n // 2) + self.maxSum(n // 3) + self.maxSum(n // 4), n)


import math

def oI(n):
	return int(math.modf(n)[1])

def solution(num, dp):
	if num <= 7:
		return num
	if dp.get(num):
		return dp[num]
	res = solution(oI(num / 2), dp) + solution(oI(num / 3), dp) + solution(oI(num / 4), dp)
	dp[num] = max(res, num)
	return dp[num]

class Solution:

	def maxSum(self, n):
		return solution(n, {1: 1, 2: 2, 3: 3, 4: 4, 5: 5})