Algorithm to form nested pairs from a number list

Question

For example, given a numbers list

sample output: 0120383****2919 ie. 1,1 2,2 3,3 max. number is 3

How to use an algorithm to form a maxmum number of nested paris?

Answer 1

Similar to Longest Palindromic Subsequence, I guess . O(n*n) solution is out there . Is that what you want ?
The exact procedure is => The problem can be solved using a recurrence relation as follows,
T(i,j) => what is the length of longest nested pair in the sub-array [i,j].
Now your answer is t(0,n-1) assume array has N elements, indexed from 0 to n-1.
T(i,j) = >
If(i>=j) T(i,j) = 0
If(arr[i] == arr[j]) T(i,j) = 2+T(i+1,j-1)
else T(i,j) = max(T(i+1,j),T(i,j-1))

Now you can either write a recursive or a bottom up DP to solve the recurrence. NOTE that while solving the recurrence you will also have to trace which Segment gave the maximum answer, and then you just need to traverse that segment and collect all matching pairs.

Answer 2

Here is a working algorithm I wrote in R. While this works it's overly verbose because I'm tired.

I can come back tomorrow and make it shorter if you need, but hopefully you can just see the logic and then make your own version in whatever language.

# Example data
num_list <- c(0,1,2,0,3,8,3,2,9,1,9)

# Declare empty vector for later
tmp <- numeric()

# Find out which numbers can be ruled out based on frequency
cnt <- as.data.frame(table(num_list))

# Keep pairs, fix data classes
for(i in unique(cnt$num_list)){
  if(cnt$Freq[cnt$num_list==i] == 2){
    tmp <- c(as.numeric(as.character(
      cnt$num_list[cnt$num_list == i])), tmp)    
  }  
}

num_list <- num_list[num_list%in%tmp]

# Figure out where the max (peak) number is, to cut the data 
peak <- numeric()
for(i in 1:(length(num_list)-1)){
  if(!is.na(num_list[i]) & num_list[i] == num_list[i+1]){
    peak <- num_list[i]
  }
}

# Apply nesting filter to first half of data
drop <- numeric()
for(i in 1:(length(num_list)-1)){
  if(!is.na(num_list[i]) & num_list[i] == peak){
    break
  } else if(!is.na(num_list[i]) & num_list[i] > num_list[i+1]){
    num_list[i+1] <- NA
  }
}

num_list <- num_list[!is.na(num_list)] 
num_list <- num_list[!num_list %in% 
                     unique(num_list)[table(num_list)==1]]

num_list.beg <- num_list[1:(max(which(num_list==peak)))]
num_list.end <- num_list[(max(which(num_list==peak))+1):length(num_list)]

# Apply nesting filter to second half of data     
for(i in 1:(length(num_list.end)-1)){
 if(!is.na(num_list.end[i]) & num_list.end[i] <= num_list.end[i+1]){
   num_list.end[i+1] <- NA
  }
}

num_list.end <- num_list.end[!is.na(num_list.end)]
num_list     <- c(num_list.beg, num_list.end)

# Sort them like you did in your desired output
sort(num_list)

1 1 2 2 3 3