Let the solution for a given number n is defined by `sol(n)`

We can break `n`

in following ways:

(1, n - 1), (2, n - 2) ... (n - 1, n)

In general we can define this as `(i, n - i)`

for all `i`

in `[1..(n - 1)]`

We need to consider all of these `n - 1`

possibilities

Hence recurrence relation for the solution can be defined as follows:

```
sol(n) = max(i * (n - i), i * sol(n - i)) for all i in [1..(n - 1)]
```

Now we need to define the base cases for this solution

It is easy to verify that:

```
sol(1) = 1 #reasonable assumption
sol(2) = 1
```

Now we can compute the required solution bottom up:

```
int solve(int n) {
int[] mem = new int[n + 1]
if(n <= 2) return 1;
mem[0] = 1;
mem[1] = 1;
for(i = 3; i <= n; i++)
for (j = 1; j < i; j++) {
mem[i] = j * (i - j);
if(j * mem[i - j] > mem[i])
mem[i] = j * mem[i - j];
}
return mem[n];
}
```