I am trying to improve my dynamic programming skills and I have read CLRS book on the Dynamic Programming chapter over the weekend and believe I understood all the concepts presented there, including the characteristics that the problem needs to have to be tackled by the use of DP.
I believe that Sum of Pairs (code PAIRSUM, difficulty easy) is one such problem and I want to use it to learn more and improve my DP skills.
So, in this specific problem, I think that we can identify the subproblems as considering a subarray say X(i,j) starting at index i and ending at index j, such that the original problem we want to solve is finding the largest sub-array that is good on the whole array, i.e., X(0,N-1), if the original array’s size is N.
I also think that the subarray we are to find needs to be of even length due to the N/2 subarrays condition.
The optimal substructure also raises as a sub-array of size say, 8, will contain in itself the good arrays of sizes 6 and 4 respectively, with 4 being the minimum possible size of a sub-array…
Can anyone please give me some hints so I can get on track in this problem?
That would be wonderful for me to improve my skills.
Thanks in advance,