**Setter:** Soham Chakrabarti

**Tester:** Sunita Sen

**Editorialist:** Soham Chakrabarti

# DIFFICULTY

Easy - Medium

# PREREQUISITES

Dynamic Programming

# PROBLEM

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.

# EXPLANATION

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!
```

# TIME COMPLEXITY

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

# SOLUTIONS

## Setter's Solution

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