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?