O(n) DP(no recursion) 100ms
```\nint integerBreak(int n) {\n        if(n==2)\n            return 1;\n        int ans[n+1];\n        ans[0]=0;\n        ans[1]=1;\n        ans[2]=1;\n       
```\nint integerBreak(int n) {\n        if(n==2)\n            return 1;\n        int ans[n+1];\n        ans[0]=0;\n        ans[1]=1;\n        ans[2]=1;\n        ans[3]=2;\n        for(int i=4;i<=n;i++)\n        {\n            ans[i]=i;\n            for(int j=1;j<i;j++)\n            {\n                //these two values of x and y are precalculated becase think logically if j or i-j                     \n\t\t\t\t//being 1,2 or 3 max answer would be that number \n                //unlike 5 6 7... where max ans are like 2*3,3*3,3*4...\n                int x=j<=3?j:ans[j];\n                int y=i-j<=3?i-j:ans[i-j];\n                ans[i]=max(ans[i],x*y);\n            }\n        }\n        return ans[n];\n    }
['Dynamic Programming']