ECJAND - Editorial


Setter: Soham Chakrabarti
Tester: Sunita Sen
Editorialist: Soham Chakrabarti


Easy - Medium


Dynamic Programming


Given an array of integers of size N and you have to partition the array into exactly K parts. For every single partition - calculate the Greatest Common Divisor.
Sum up all the G.C.D Values and maximize the sum.


The best score can only be achieved by formulating for all possible states and using a cache to store the data processed already.
We will be using recursion for this case and memorize the data on the way.

states to remember
Let's consider the states of our memorizing table to be :

1. index i of the element in the original array.

2. K-th partition which the element has been placed.

Therefore, we can clearly have a look at our 2d state. 

Now, we progress, with the recursive formula.

We start our recursion with the first element and loop through the elements of the array. While we loop, we also calculate the G.C.D till the i-th element.
For every element we get while looping, we recurse down to a step further, by placing it in a partition Below is the snippet to do so :

snippet to recurse
for(int j = i; j < size_of_array ; ++j) {
   gcdTillith = gcd (gcdTillith, array[i]);
   int res = recurse(j + 1, k - 1) // calculate for the next index and reduce k as we add a partition
What about the base cases ?

There could be two cases down here :

base case 1
When our index reaches the $N$, the size of the array, it means this is the 
last state, we have reached the end. In this state, if our $k$ is greater than 0, 
it means we have to still partition the data, but we cannot and thus we can 
return a large value, since it will get neglected while formulate the maximum 
score in our previously called function.

However if, we reach end and out k is also equal to 0, it means, we have 
successfully partitioned the array and now we will have to consider the 
state. So we can return a 0 for this case. The zero signifies add up the 
previous state values and get a result. 
base case 2
If we are not at the end of our array, but still we reach a value of K = 0, we 
will have to return a large value again. 
Why ? think a bit!


The Time complexity will be O(K.N^2)


Setter's Solution


Feel free to share your approach. Suggestions are welcomed as always. :slight_smile: