343. Integer Break

 一刷 06/2022

Version #1 DP

Time O(N^2)

Space O(N)

Runtime: 2 ms, faster than 25.67% of Java online submissions for Integer Break.

Memory Usage: 40.9 MB, less than 43.50% of Java online submissions for Integer Break.

class Solution {

    public int integerBreak(int n) {

        long[] dp = new long[n + 1];

        dp[1] = 1;

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

            dp[i] = i - 1; // split i into 1 and i - 1

            for (int diff = i - 1; diff >= i / 2; diff--) {

                dp[i] = Math.max(dp[i], Math.max(dp[i - diff], i - diff) * Math.max(dp[diff], diff));

            }

        }

        return (int)dp[n];

    }

}