Problem Link - Indraneels Experiment
Problem Statement
Indraneel’s student has given him data from two sets of experiments that the student has performed. Indraneel wants to establish a correlation between the two sets of data. Each data set is a sequence of N numbers. The two data sets do not match number for number, but Indraneel believes that this is because data has been shifted due to inexact tuning of the equipment.
For example, consider the following two sequences:
3 8 4 23 9 11 28
2 3 22 26 8 16 12
Indraneel observes that if we consider the subsequences 3,~4,~23,~9 and 2,~3,~22,~8 and examine their successive differences we get 1,~19,~−14. He considers these two subsequences to be “identical”. He would like to find the longest such pair of subsequences so that the successive differences are identical. Your task is to help him do this.
Approach
The task is to identify pairs of subsequences that share the same successive differences between corresponding elements. To solve this, a dynamic programming approach is used. A 2D table L is maintained, where L[i][j] represents the length of the longest matching subsequences ending at indices i in the first sequence and j in the second sequence. Another table P stores the parent indices for reconstructing the subsequences. For each pair of starting and ending indices in the sequences, the differences are compared. If the differences match, the subsequence lengths are updated in L, and the corresponding parent indices are stored in P. Finally, the maximum length is determined, and the subsequences are reconstructed by tracing back through the parent table.
Time Complexity
The approach has a time complexity of O(N^4), as it involves nested loops iterating through all possible pairs of start and end indices.
Space Complexity
The space complexity is O(N^2) due to the storage of the L and P tables, each of size N×N.