Integer Break for max product

Problem: Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example:

Input: 3
Output: 2
Explanation: 3 = 2 + 1, 2 × 1 = 1.

Approach: We can use DP here. We can maintain a 1D Table where Table[i] will tell the maximum product by breaking i into at least 2 part. Obviously Table[n] will be our answer. Here is how we can fill this table:

• Table[0] = Table[1] = 0
• At any number i we need to get the maximum product of every partition of i possible. That means we need to run another loop say j = 1 to i - 1. Now at every j, here are the four products (partitions) possible:
1. j * (i - j)
2. maxProduct(j) * (i - j)
3. j * maxProduct(i - j)
4. maxProduct(j) * maxProduct(i - j)
• Right so for every j we can take the maximum of all the above 4 products and that will be maximum product of partitions if divide i at j. Obviously the maximum of maximum products of all the 'j's will maximum product for number 'i'.
• Once we understand the above logic. It's easy to understand the algorithm now:
• FOR i = 2 to n
• maxProd = 0
• FOR j = 1 to i - 1
• currMaxProd = Max ( j * (i - j), Table[j] * (i - j), j * Table[i - j], Table[j] * Table[i - j] // Max of the 4 products
• maxProd = Max(currMaxProd, max)
• Table[i] = maxProd

Hopefully its clear now.

Implementation in C#:

        public static int IntegerBreak(int n)

        {

            int[] table = new int[n + 1];

            for (int i = 2; i <= n; ++i)

            {

                int maxProd = 0;

                for (int j = 1; j < i; ++j)

                {

                    int currMaxProd = Max(table[j] * table[i - j], j * table[i - j], table[j] * (i - j), j * (i - j));

                    maxProd = Math.Max(maxProd, currMaxProd);

                }

                table[i] = maxProd;

            }

            return table.Last();

         }

        public static int Max(params int[] values)

        {

            return Enumerable.Max(values);

        }

        

Complexity: O(n^2)