# Why is this problem listed as “Dynamic Programming”

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?

• 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. – Euge Oct 14 '16 at 23:29
• @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. – loremIpsum1771 Oct 14 '16 at 23:59