Simple explanation with diagrams | DP + Recursion | O(n)
---\n\n\n\n---\n## FOCUS\nINTEGER SUM of 2 : (1+1)\nINTEGER SUM of 4 : (1+1+1+1), (1+1+2), (1+3), (2+2)\n\nImportant observation : we need to get maximum value 
---\n\n![image.png](https://assets.leetcode.com/users/images/581ed7a9-7040-4c5f-bb6c-a34ae915ca5a_1696608720.2271945.png)\n\n---\n## FOCUS\n**INTEGER SUM of 2 :** $$(1+1)$$\n**INTEGER SUM of 4 :** $$(1+1+1+1), (1+1+2), (1+3), (2+2)$$\n\n*Important **observation*** : we need to get ***maximum value*** from each number when current number contributes to the interger sum of a number ***greater than*** itself.\n\n**Then,**\n$$\\forall i >= 2$$\n    \n**Maximum Value**: `max(current number, value calculated using integer break i.e dp[number])`\n    **Example** : i = 2, `max(2, dp[2]) = max(2,1)`\n*Maximum value* : **2**\n    \n![image.png](https://assets.leetcode.com/users/images/3e7138bd-2ad3-4d79-a7d7-1841426433d6_1696608747.7516265.png)\n\n\n---\n### n = 3\n`(1 + 2)`\n\n![image.png](https://assets.leetcode.com/users/images/831ca342-7d36-47fc-82df-dab1883582e5_1696608772.0919096.png)\n\n\n### n = 4\n\n`(1 + 3), (2 + 2)`\n\n![image.png](https://assets.leetcode.com/users/images/f2916428-0f5e-4e0f-a0d3-96eb96085a68_1696608791.8327537.png)\n\n\n### n = 5\n\n`(1 + 4), (2 + 3)`\n\n![image.png](https://assets.leetcode.com/users/images/da788019-fd2c-420d-9a14-60dbaea3cefe_1696608825.4320703.png)\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\n    int sol(int num, vector<int>&dp){\n        if(num < 2 )return 1;\n\n        //IMPORTANT OBSERVATION POINT! Remember?\n        if(dp[num] != -1) return max(num , dp[num]);\n\n        int res = 1;\n\n        //checking all states\n        //For num = 4\n        // i = 1, res = max(res , sol(1, dp) , sol(3,dp));\n        // i = 2, res = max(res , sol(2,dp), sol(2, dp))\n        //refer diagrams for a better understanding\n        for(int i = 1; i < num ; i ++){\n            res = max(res , sol(i , dp) * sol(num - i , dp));\n        }\n\n        //storing in dp and returning \n        return dp[num] = res;\n    }\n\n    int integerBreak(int n) {\n\n        if(n <= 2)return 1;\n        \n        vector<int>dp(n + 1, -1);\n        dp[2] = 1;\n        \n        int ans = sol(n , dp);\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C++']