Split an integer for the largest product

def integer_break(n):
    best = [1] + [0] * n                    # best[t]: a single part allowed
    for t in range(1, n + 1):
        for p in range(1, t + 1):
            if t == n and p == n:
                continue                    # n itself needs at least two parts
            best[t] = max(best[t], p * best[t - p])
    return best[n]

#include <algorithm>
#include <vector>

long long solve(int n) {
    std::vector<long long> best(n + 1, 0);
    best[0] = 1;
    for (int t = 1; t <= n; ++t)
        for (int p = 1; p <= t; ++p) {
            if (t == n && p == n) continue;             // at least two parts for n
            best[t] = std::max(best[t], p * best[t - p]);
        }
    return best[n];
}

class Solution {
    public long integerBreak(int n) {
        long[] best = new long[n + 1];
        best[0] = 1;
        for (int t = 1; t <= n; t++)
            for (int p = 1; p <= t; p++) {
                if (t == n && p == n) continue;           // at least two parts for n
                best[t] = Math.max(best[t], p * best[t - p]);
            }
        return best[n];
    }
}

function integerBreak(n) {
  const best = [1, ...new Array(n).fill(0)];
  for (let t = 1; t <= n; t++)
    for (let p = 1; p <= t; p++) {
      if (t === n && p === n) continue;           // at least two parts for n
      best[t] = Math.max(best[t], p * best[t - p]);
    }
  return best[n];
}

fn solve(n: i64) -> i64 {
    let n = n as usize;
    let mut best = vec![0i64; n + 1];
    best[0] = 1;
    for t in 1..=n {
        for p in 1..=t {
            if t == n && p == n {
                continue;                               // at least two parts for n
            }
            best[t] = best[t].max(p as i64 * best[t - p]);
        }
    }
    best[n]
}

import Data.Array

solve :: Int -> Int
solve n = maximum [p * best ! (n - p) | p <- [1 .. n - 1]]   -- at least two parts for n itself
  where
    -- best ! t: the largest product of parts summing to t, a single part allowed
    best = listArray (0, n) (1 : [maximum [p * best ! (t - p) | p <- [1 .. t]] | t <- [1 .. n]]) :: Array Int Int