javascript-data-structures-and-algorithms/src/dynamic-programming/1d/integer-break/integerBreak.js at master · evgenirusev/javascript-data-structures-and-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
 * https://leetcode.com/problems/integer-break
 * @param {number} n
 * @return {number}
 */

// Bottom up DP
// Time complexity - O(n^2)
// Space complexity - O(n)
function integerBreak(n) {
    if (n <= 3)
        return n - 1;

    const dp = Array(n + 1).fill(0);

    for (let i = 1; i <= 3; i++)
        dp[i] = i;

    for (let num = 4; num <= n; num++) {
        let ans = num;

        for (let i = 2; i < num; i++)
            ans = Math.max(ans, i * dp[num - i]);

        dp[num] = ans;
    }

    return dp[n];
}

// Top down DP approach
// Time complexity - O(n^2)
// Space complexity - O(n)
// function integerBreak(n) {
//     const dp = new Array(n + 1).fill(0);

//     function dfs(num) {
//         if (num <= 3)
//             return num;

//         if (dp[num] !== 0)
//             return dp[num];

//         let res = num;
//         for (let i = 2; i < num; i++) {
//             const r = i * dfs(num - i);
//             res = Math.max(res, r);
//         }

//         dp[num] = res;
//         return res;
//     }

//     if (n <= 3)
//         return n - 1;

//     return dfs(n);
// }

// Brute force backtracking dfs
// Time complexity - O(2^n)
// Space complexity - O(n)
// var integerBreak = function(n) {
//     if (n === 3)
//         return 2;
//     if (n === 5)
//         return 6;

//     let maxVal = 1;
//     const maxMultiplicationVal = Math.floor(n / 2);
//     const set = [];

//     function dfs(i) {
//         if (i > maxMultiplicationVal || set.reduce((sum, num) => (sum + num), 0) > n)
//             return;

//         const product = set.reduce((sum, num) => { return sum * num }, 1);
//         if (product > maxVal) {
//             maxVal = product;
//         }

//         for (let j = i; j <= maxMultiplicationVal; j++) {
//             set.push(j);
//             dfs(j)
//             set.pop(j);
//         }
//     }

//     dfs(2);

//     return maxVal;
// };

module.exports = integerBreak;