343. Integer Break

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 1:

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

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

Rust Solution

struct Solution;
use std::collections::HashMap;

impl Solution {
    fn integer_break(n: i32) -> i32 {
        let mut memo: HashMap<(i32, bool), i32> = HashMap::new();
        Self::dp(n, true, &mut memo)
    }

    fn dp(n: i32, split: bool, memo: &mut HashMap<(i32, bool), i32>) -> i32 {
        if let Some(&res) = memo.get(&(n, split)) {
            return res;
        }
        let mut res = if split { 0 } else { n };
        for i in 1..n {
            res = res.max(i * Self::dp(n - i, false, memo));
        }
        memo.insert((n, split), res);
        res
    }
}

#[test]
fn test() {
    let n = 2;
    let res = 1;
    assert_eq!(Solution::integer_break(n), res);
    let n = 10;
    let res = 36;
    assert_eq!(Solution::integer_break(n), res);
}

Having problems with this solution? Click here to submit an issue on github.