Help regarding sum of pairs

general
, , ,
1

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? :slight_smile:

That would be wonderful for me to improve my skills.

Thanks in advance,

Bruno

1 Like
2

In this problem we should deal with subsequences that can be not consecutive. So subarray idea is inapplicable here. This problem requires some sorting and searching ideas. For example you can iterate over all values of Y[i]+Y[j] and for each such value V find the largest good subsequence by simple search for each Y[i] the value V-Y[i] in the array. But some careful dealing is required due to repetitions.

In fact we can solve this problem by DP with subarrays but complexity will be higher. The main thing is that we should do this DP for the fixed value of V described above. Namely if DP[i,j] is the size of the maximal subsequence with value V on the segment [i,j] of the sorted array Y then
DP[i,j] = max{DP[i+1,j], DP[i,j-1], DP[i+1,j-1] + (Y[i]+Y[j]==V?1:0)}.
With initial values DP[i][j]=0 for i>=j.