Given 2 finite strictly increasing sequences, find a path through the intersections that produces the greatest sum.

Problem Statement: (suggested by a friend) You have been given two finite strictly increasing sequences of numbers. Intersections are all the numbers that are common in both the sequences. For example,

First= 3 5 7 9 20 25 30 40 55 56 57 60 62
Second= 1 4 7 11 14 25 44 47 55 57 100

You can see the intersection numbers in bold. So now you are allowed to “walk” over this sequence in 2 ways,

1. You may start at the beginning of any of the two sequences. Now start moving forward.
2. At each intersection point, you have the choice of either continuing with the same sequence you’re currently on, or switching to the other sequence.

(This is kind of like the Machine Scheduling problem we tackle while dealing with Dynamic Programming. However, we’ll come to that a little later. Not today, for sure.)

The objective is finding a path that produces the maximum sum of data you walked over. In the above example, the largest possible sum is 450  which is the result of adding 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, and 62.

Just taking a quick look at the problem, you realize that it can be done in O(n) time. All that remains is asking the big question: how? Once again, it isn’t very difficult. Here is the algorithm you should follow for 2 sequences A and B and it should be easy. Consider the following declarations,

1. CURRENT_A=0, CURRENT_B=0

2. SUM_A=0, SUM_B=0

3. INTERSECTON_A ={-1} , INTERSECTION_B = {-1} //containing intersection positions with initially 0 in both

//The ADD signifies adding a value to the end of a list

4. FINAL_SUM=0

WHILE (1)

{

IF(CURRENT_A == END_A OR CURRENT_B==END_A) //if either counter reaches end of that particular array

{

Break out of LOOP

}

IF( A[CURRENT_A] > B[CURRENT_B] )

{ //if current of A is greater than current of B, find sum of B till this point in this window and increment its counter

SUM_B = SUM_B + B[CURRENT_B]

CURRENT_B = CURRENT_B + 1

}

ELSE IF( A[CURRENT_A] < B[CURRENT_B] )

{  //if current of B is greater than current of A, find sum of A till this point in this window and increment its counter

SUM_A = SUM_A + A[CURRENT_A]

CURRENT_A = CURRENT_A + 1

}

ELSE IF ( A[CURRENT_A] == B[CURRENT_B] )

{  //if both are equal, found intersection

IF (SUM_A > SUM_B)

{ //if in this particular window, sum of A is greater than of B, add path A (represented as 0) to array and the intersection positions

PATH.ADD(0)

INTERSECTION_A.ADD( CURRENT_A )

INTERSECTION_B.ADD( CURRENT_B )

}

ELSE

{ //if in this particular window, sum of B is greater than of A, add path B (represented as 1) to array and the intersection positions

PATH.ADD(1)

INTERSECTION_A.ADD( CURRENT_A )

INTERSECTION_B.ADD( CURRENT_B )

}

SUM_A=SUM_B=0 

CURRENT_A=CURRENT_A+1

CURRENT_B=CURRENT_B+1

//for the next window, we set sums of A and B to zero and increment counters

}

}

// one of the arrays is done and we are out of the while loop

//Next, we find the remaining elements in the window of the array with remaining elements if any and find the appropriate last window to add

WHILE (CURRENT_A not equal to END_A)

{

SUM_A = SUM_A + A[CURRENT_A]

CURRENT_A = CURRENT_A + 1

}

WHILE (CURRENT_B not equal to END_B)

{

SUM_B = SUM_B + B[CURRENT_B]

CURRENT_B = CURRENT_B + 1

}

IF ( SUM_A > SUM_B )

{

PATH.ADD(0)

INTERSECTION_A.ADD( CURRENT_A )

INTERSECTION_B.ADD( CURRENT_B )

}

ELSE

{

PATH.ADD(1)

INTERSECTION_A.ADD( CURRENT_A )

INTERSECTION_B.ADD( CURRENT_B )

}

//now we simply check path(0/1) and corresponding intersections to get the required path

FOR ( i=0; i<PATH.SIZE ; i++)

{

IF ( PATH[i] == 0 )

{

FOR( j=INTERSECTION_A[i]+1 ; j<=INTERSECTION_A[i+1]; j=j+1)

{

PRINT A[j]

FINAL_SUM = FINAL_SUM+A[j]

}

}

ELSE

{

FOR( j=INTERSECTION_B[i] +1; j<=INTERSECTION_B[i+1]; j=j+1)

{

PRINT B[j]

FINAL_SUM = FINAL_SUM+B[j]

}

}

}

PRINT FINAL_SUM

Yes, it might have been a little long but go over it and you’ll find it pretty simple to comprehend. We take the sum of both the arrays till we find an intersection and at that point check which sum is greater hence building a solution till there. We then proceed likewise for the values starting from this intersection to the next. This is in essence a Dynamic Programming approach to the problem. 🙂

Well, I guess my next post will have to be about Dynamic Programming then. All eyes!