1
$\begingroup$

I found a problem in the dynamic programming section of hackerrank but its not clear why dynamic programming should be used to solve it. The problem is as follows:

Nikita just came up with a new array game. The rules are as follows: Initially, there is an array, , containing integers. In each move, Nikita must partition the array into non-empty parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets point; otherwise, the game ends. After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array . Nikita loves this game and wants your help getting the best score possible. Given , can you find and print the maximum number of points she can score?

In going over the algorithm that would be used to solve the problem, it seemed evident to me that you could simply write a recursive function where each recursive call would be made iff the sums of the elements in both halves of the array are equal. Otherwise, the game (the algorithm) ends. Since you would, in the worst case (running time wise), be dividing the array log(n) times where n is the array length, you would get a running time of O(logn).

The only thing that I could see dynamic programming helping with here may be the recalculation of the sums which I guess could be avoided by calculating the sums from the bottom up but I'm not really seeing an optimal substructure here. Also, you would be increasing the space complexity seemingly unnecessarily.

So why/how is dynamic programming being used here?

Improve this question
$\endgroup$
2
  • $\begingroup$ First, if you need to calculate the sum of the whole array, for sure that it can't be done in $O(log\ n)$ time. Then, let's say that you mean that the maximun number of points she can get is $log\ n$, which is also false (for example, if the array is always divided leaving only one value out). The best solution is using dynamic programming because you need to calculate n different sums in each step. And once you calculate the sum which divides the array, you need to recalculate the sums for the next step again, so it is convenient to have them already stored. $\endgroup$
    – Euge
    Oct 14, 2016 at 23:29
  • $\begingroup$ @Euge Oh of course! For some reason, I was thinking that the addition would be constant time but it obviously would be linear. What would the running times of the algorithm be with and without dynamic programming. $\endgroup$
    – loremIpsum1771
    Oct 14, 2016 at 23:59

1 Answer 1

Reset to default
2
$\begingroup$

How do you choose which partition is best (there could be several partitions if you allow negative numbers or zeroes), and which side of the partition to choose? You have to examine all partitions and both sides of each partition, and then choose the best one. Naively, the complexity of this algorithm is exponential. With dynamic programming you can find the solution in polynomial time – I'll let you figure out how.

Improve this answer
$\endgroup$
1
  • $\begingroup$ oh, for some reason, I was thinking that the problem called for dividing the array directly in half but its actually a partitioning problem which can be solved with DP. $\endgroup$
    – loremIpsum1771
    Oct 15, 2016 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.