Hi, I was trying to solve this problem. And after going through a couple of submissions (Here is a neat one) I got the transition recurrence but I am still not able to work around the intuition behind it. Can someone please explain a little about what are the pointers which lead you this recurrence and also I am sorry if it’s a standard dp type(if possible please share some resource or problem based on the same idea :P) @everule1
1 Like
Hi
I can understand your problem. I would recommend you to have a look at the recursive solution for a better understanding.
Let me explain the approach :
In our recursive function we pass two parameters (i, k) and dp(i, k) means the maximal sum obtained from [i:n] where i is on the k - th partition.
We loop through every element starting from i, keep gcd-ing the value and for every index check the result of the next index.
Let us take an array [2, 4, 5 ,3 ,6] and K = 3
Following is a vivid description of the recursion. You can simply memorize the (i, k) states and get an accepted solution. 
Check out the diagram
4 Likes
Thanks for such a detailed explanation. This was exactly what I was looking for. I Highly appreciate it.
1 Like
Thanks! Glad I could help. 