How to determine the longest increasing sub-sequence using dynamic programming with joinable input integers

1
votes

I read the article about How to determine the longest increasing sub-sequence using dynamic programming with this algorithm:

int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;

for (int i = 1; i < N; i++)
{
   DP[i] = 1;
   prev[i] = -1;

   for (int j = i - 1; j >= 0; j--)
      if (DP[j] + 1 > DP[i] && array[j] < array[i])
      {
         DP[i] = DP[j] + 1;
         prev[i] = j;
      }

   if (DP[i] > maxLength)
   {
      bestEnd = i;
      maxLength = DP[i];
   }
}

but i want to know how to solve this problem with this condition that we can take the arrays with joined integers.

For example: 1,5,3,1,5,6,7,8,1,2,9
we can have this set:1,3,5,6,7,8,12 for solution
that 12 is joint form 1 and 2

so conditions are: The input array includes 1-9 numbers! and the integers can joined from few other integers.

1
algorithmcomputer-sciencedynamic-programminglis
How do you measure the length of the subsequence? Would 12 count as 1 or 2 elements? - Scott Hunter
@ScottHunter the 12 is one element, so we have 7 length set there - iman
So in your example, 1,3,5,6,7,8,9 and 1,3,5,6,7,8,12 would both be solutions. - Scott Hunter
so all the elements of array[i] are single digit numbers? - CS Pei
@JohnSmith yes the input array is single digit numbers but the answer could be multiple digit array - iman

1 Answers

2
votes

Original problem

dp[i] = max(DP[j] + 1, a[j] < a[i])

Your problem

Let:

a[x,y] = a[x] + a[x + 1] + ... + a[y] (+ means concatenate)

So:

f[x,y] = max(DP[j] + 1, a[j] < a[x,y], j < x)
dp[i] = max(f[i,j], 0 <= j <= i) = max(
   max(DP[j] + 1, a[j] < a[i], j < i) # f(i, i)
   max(DP[j] + 1, a[j] < a[i-1, i], j < i - 1) # f(i-1, i)
   ...
)

If you still have some problems, please don't hesitate to leave a comment here.