use std::cmp::max;

struct Solution {}
impl Solution {
    pub fn integer_break(n: i32) -> i32 {
        let n = n as usize;
        let mut dp = vec![0; (n + 1) as usize];
        if n <= 3 {
            return (n - 1) as i32;
        }
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for i in 4..=n {
            for j in 1..i {
                dp[i] = max(dp[i], dp[i - j] * dp[j])
            }
        }
        dp[n]
    }
}
#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test() {
        assert_eq!(Solution::integer_break(10), 36);
    }
}