Given a rope of length N meters, cut the rope into several ropes of varying lengths in a way that maximizes product of lengths of all resulting ropes. You must make at least one cut.
Example 1:
Input:
N = 2
Output: 1
Explanation: Since 1 cut is mandatory.
Maximum obtainable product is 1*1 = 1.
Example 2:
Input:
N = 5
Output: 6
Explanation: 
Maximum obtainable product is 2*3 = 6.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxProduct() which takes n as input parameter and returns the maximum product.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def maxProduct(self,n):

        # code here

Solutions:
class Solution:

	def maxProduct(self, n):
		dp = [0] * (n + 1)
		dp[1] = 0
		for i in range(2, n + 1):
			for j in range(1, i):
				dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
		return dp[n]


import collections

class Solution:

	def maxProduct(self, n):
		dp = collections.defaultdict(int)

		def recur(k):
			if k == 1:
				return 1
			if k in dp:
				return dp[k]
			max_prod = 0
			for i in range(1, k):
				max_prod = max(max_prod, recur(i) * recur(k - i))
			dp[k] = max(k, max_prod)
			return dp[k]
		max_prod = 0
		for i in range(1, n):
			max_prod = max(max_prod, recur(i) * recur(n - i))
		return max_prod


class Solution:

	def maxProduct(self, n):
		if n < 7:
			i = n // 2
			j = n - i
			return i * j
		if n % 3 == 0:
			return 3 ** (n // 3)
		if n % 3 == 2:
			return 3 ** (n // 3) * 2
		return 3 ** (n // 3 - 1) * 4


class Solution:

	def maxProduct(self, n):
		dp = [0] * (n + 1)
		if n == 1:
			return 0
		dp[0] = 0
		dp[1] = 0
		dp[2] = 1
		if n <= 2:
			return dp[n]
		else:
			for i in range(3, n + 1):
				max = -1
				for j in range(1, i):
					now = dp[j]
					if dp[j] < j:
						now = j
					if max < now * (i - j):
						max = now * (i - j)
				dp[i] = max
			return dp[n]


class Solution:

	def maxProduct(self, n):
		t = [0 for i in range(n + 1)]
		for i in range(n + 1):
			if i == 0 or i == 1:
				t[i] = 0
		for i in range(1, n + 1):
			max_val = 0
			for j in range(1, i):
				max_val = max(max_val, j * (i - j), j * t[i - j])
			t[i] = max_val
		return t[n]


class Solution:

	def maxProduct(self, n):
		if n <= 3:
			return n - 1
		dp = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			maxi = 0
			for j in range(1, i):
				maxi = max(maxi, (i - j) * j, j * dp[i - j])
				dp[i] = maxi
		return dp[n]


class Solution:

	def maxProduct(self, n):
		if n == 1:
			return 0
		dp = [0] * n
		dp[0] = 1
		for i in range(n):
			actualLength = i + 1
			endPoint = actualLength // 2
			for j in range(1, endPoint + 1):
				max1 = max(dp[j - 1], j)
				max2 = max(dp[actualLength - j - 1], actualLength - j)
				temp = max1 * max2
				dp[i] = max(dp[i], temp)
		return dp[-1]


class Solution:

	def maxProduct(self, n):
		if n == 1:
			return 0
		dp = []
		for i in range(n):
			dp.append([-1] * (n + 1))
		for i in range(n):
			dp[i][0] = 1
		for i in range(n + 1):
			dp[0][i] = 1
		for i in range(1, n):
			for j in range(1, n + 1):
				if i <= j:
					dp[i][j] = max(dp[i][j - i] * i, dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n - 1][n]


class Solution:

	def f(self, n, dp):
		if n <= 1:
			return 0
		if dp[n] != -1:
			return dp[n]
		max_product = 0
		for l in range(1, n):
			res = max(l * (n - l), l * self.f(n - l, dp))
			max_product = max(max_product, res)
		dp[n] = max_product
		return dp[n]

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


class Solution:

	def maxProduct(self, n):
		product = 1
		if n < 4:
			n -= 1
		while n > 4:
			product *= 3
			n -= 3
		return product * n


class Solution:

	def maxProduct(self, n):
		ans = 0
		for i in range(2, n + 1):
			(a, b) = (n // i, n % i)
			ans = max(ans, (a + 1) ** b * a ** (i - b))
		return ans


class Solution:

	def maxProduct(self, n):
		if n == 1:
			return 0
		dp = [float('-inf')] * (n + 1)
		dp[0] = 0
		dp[1] = 0
		dp[2] = 1
		for i in range(3, n + 1):
			for j in range(1, i):
				dp[i] = max(dp[i], dp[i - j] * j, (i - j) * j)
		return dp[n]


class Solution:

	def maxProduct(self, n):
		val = [0 for _ in range(n + 1)]
		for i in range(1, n + 1):
			max_val = 0
			for j in range(1, i):
				max_val = max(max_val, (i - j) * j, j * val[i - j])
			val[i] = max_val
		return val[n]


class Solution:

	def maxProduct(self, n):
		if n == 1:
			return 0
		memo = {}
		memo[2] = 1

		def recProduct(n):
			if n == 1:
				return 1
			if n in memo:
				return memo[n]
			else:
				m = 0
				for i in range(1, n):
					m = max((i * recProduct(n - i), i * (n - i), m))
				memo[n] = m
				return m
		return recProduct(n)


class Solution:

	def maxProduct(self, n):
		dp = [-1] * (n + 1)
		dp[0] = 0
		if n == 1:
			return 0
		dp[1] = 0
		dp[2] = 1
		mx = 0

		def func(n, mx):
			if dp[n] != -1:
				return dp[n]
			for i in range(1, n):
				mx = max(mx, i * (n - i), i * func(n - i, mx))
			dp[n] = mx
			return dp[n]
		func(n, mx)
		return dp[n]


class Solution:

	def maxProduct(self, n):
		dp = [1] + [0] * n
		for i in range(n + 1):
			for j in range(1, n):
				if i + j <= n:
					prod = j * dp[i]
					if prod > dp[i + j]:
						dp[i + j] = prod
		return dp[n]


class Solution:

	def maxProduct(self, n):
		if n == 1:
			return 0

		def prod(n):
			res = 1
			for i in n:
				res *= i
			return res
		dp = [0] * (n + 1)
		dp[0] = 1
		for i in range(n + 1):
			for j in range(1, n):
				if i + j <= n:
					comb = j * dp[i]
					if dp[i + j] is None or dp[i + j] < comb:
						dp[i + j] = comb
		return dp[n]
		res = 1
		for i in dp[n]:
			res *= i
		return res


class Solution:

	def maxProduct(self, n):
		if n == 1:
			return 0
		if n == 2 or n == 3:
			return n - 1
		res = 1
		while n > 4:
			n -= 3
			res *= 3
		return n * res


class Solution:

	def maxProduct(self, n):
		if n == 0:
			return 0
		dp = [0] * (n + 5)
		dp[0] = 1
		for i in range(n):
			for j in range(1, n):
				if i + j <= n:
					dp[i + j] = max(dp[i + j], dp[i] * j)
		return dp[n]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		ob = Solution()
		ans = ob.maxProduct(n)
		print(ans)
		tc -= 1


class Solution:

	def maxProduct(self, n):
		if n == 1:
			return 0
		dp = [[None for j in range(n + 1)] for i in range(n)]
		val = list(range(1, n))
		for i in range(0, n):
			for j in range(0, n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 1
		for i in range(1, n):
			for j in range(1, n + 1):
				if val[i - 1] <= j:
					dp[i][j] = max(val[i - 1] * dp[i][j - val[i - 1]], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[-1][-1]


class Solution:

	def maxProduct(self, n):
		if n == 1:
			return 0
		(rows, cols) = (n + 1, n + 1)
		arr = [[1 for i in range(cols)] for j in range(rows)]
		for i in range(n + 1):
			for j in range(n + 1):
				if j < i:
					arr[i][j] = max(arr[i][j - 1], j * arr[i - j][j], j * (i - j))
				else:
					arr[i][j] = arr[i][j - 1]
		return arr[n][n]