Given an array A of size N. Find the minimum number of operations needed to convert the given array to Palindromic Array
The only allowed operation is that you can merge two adjacent elements in the array and replace them with their sum.
Example:
Input array:
5 3 3 3
No of minimum operation: 3 (don't worry, you will know the reason soon!!)
Input array:
5 3 3 5
No of minimum operation: 0 (It's palindromic array!!)
Algorithm:
For solving the above problem a recursive algorithm can be constructed based on the following conditions.
Let array [i, j] be the subarray to be checked where I be the staring index & j be the end index
So there can be three cases,
Based on these three conditions we have constructed the recursive function:
Example with explanation:
C++ implementation:
Output