How we can break 'n' into parts such that LCM of parts is maximum (number of parts should be greater than or equal to 2)? OR Find A1, A2, ..., Ak such that A1 + A2 + ... + Ak = n and LCM(A1, A2, ..., Ak) is maximum. Here 2 <= k <= n. Original Problem Link: http://acm.timus.ru/problem.aspx?space=1&num=1807

There is another important requirement in the original problem: first, GCD of all numbers should be the maximum possible. LCM should be maximized among such answers only.

Yeah. Maximum GCD is the maximum number which divides n. We can find that in O(sqrt(n)). So finally we have to maximize LCM for n/(maximum number which divides n) which is the smallest prime number which divides n. So that problem reduces to the problem which I mentioned in the blog.

Did you Solve this? it seems this is some DP problem, but i am unable to solve it too. It would be great if you share the solution if you solved it, or please someone share the solution approach to this problem.