DP solution, but with explanation
   int[] dp = new int[n+1];\n        dp[1] = 1;\n        for(int i = 2; i <= n; i++) \n            for(int j = 1; j < i; j++) \n                dp[i] = Math.max
       int[] dp = new int[n+1];\n        dp[1] = 1;\n        for(int i = 2; i <= n; i++) \n            for(int j = 1; j < i; j++) \n                dp[i] = Math.max(dp[i], (Math.max(j,dp[j]) * Math.max(i-j,dp[i-j])));\n        \n        return dp[n];\n\n> dp[i] says that what the maximum product we can get for this number\n\nNow, how to get the recursion part?\n\n\nOuter loop is being used build the values of all other numbers which will be required to get to the solution and our solution will be available in dp[n]\n\nWe will check all the possible combination present, which is being accomplished by second loop.\nSo, we are looping from 1 till i and keep checking for the maximum value\n\nExample: i = 5 , so we will check for j = 1, 2, 3, 4 \n\nNow, either we can pick the number itself or we can pick the maximum we can get from combinational products, which is accomplished by Math.max(j,dp[j])\nThen we will left with a number which is equal to i - j, say we were looping for j =3 and i = 5, then we are picking j =3 (and checking if we should pick 3 or its dp solution) then the other part of 5 will be (i-j = 5 - 3 = 2) so will check the same logic for 2 and then will get their product.\n\nAnd keep updating our dp[i] with different position of j.\n\nFurther second loop can optimized to \nfor(int j = 1; 2*j < i; j++) \nfor obvious reason to remove the duplicate checks\n\nHope this helps
['Dynamic Programming', 'Java']