## 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 ﬁnding 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!

Here is my guess at how to do it using dynamic programming…

Create two tables for each, which have the sum up till that intersection element.

So obviously parsing it bottom up and building the tables will help.

Actual Sum arrays

1st = 3 7 (12) 21 41 (66) 96 136 (191) 247 (304) 364 726

2nd = 1 5 (12) 23 37 (62) 106 153 (208) (265) 365

Intersection-Sum-Tables

1st = 12 66 191 304

2nd= 12 62 208 265

Current = -1 , Next = 0

Keep checking Current and Next

Loop till either or both of the Next are not at the end

{

if Next of 1st > Next of 2nd

start on the 1st array till the Next of 1st element

if Next of 1st < Next of 2nd

start on the 2nd array till the Next of 2nd element

else // if they are equal

add the value and arbitrarily choose any one of them

}

I'm kinda weak at Dynamic Programming.. So am I correct ?

Uh. I don’t understand what 12, 66, 191, 304, 12, 62, 208, 265 are in your arrays. Please explain. Are you considering them as intersections? If yes, read the question once more. Intersections are the same numbers occurring in both sequences.

Those are sums up till the intersections in both arrays

elements intersecting with the other array are in ‘()’

I did that in a hurry so I think I messed up building those arrays.. but anyway, here is the gist of it..

First = 3 5 (7) 9 20 (25) 30 40 (55) 56 (57) 60 62

1st = { 3+5+7, 3+5+7+9+20+25, 3+5+7+9+20+25+30+40+55, 3+5+7+9+20+25+30+40+55+56+57 }

So, I’m maintaining tables of sum up till each intersection. And then using greedy to choose from the arrays depending upon the next entry in the intersection sum table.

Should work.. right?