Today we briefly revisit the bridge problem and see how to apply the longest increasing subsequence.
Let us say the cities on both sides of the river are 2, 3, 1 and 1, 2, 3.
from the previous discussions on the longest increasing subsequence, we can find it recursively by including the last element or not.
Let us keep track of the indices in an array
we take the first sequence and iterate from left to right. say i = 0
for an increasing subsequence of size j=1 and i = 0 upto and inclusive of 2, the minumum value of the length of the increasing subsequence is one greater than the length of the longest prefix at this element and now equals 1
we initialize IndexArray at 1 to be 1 and update the longest subsequence encountered so far to be 1

for an increasing subsequence of size j =1  and i = 1 upto and inclusive of 3, the minimum value by binary search is that for first element plus 1 which now equals 2

for the last element, the binary search points to the second element and has not changed  the length L computed so far and updated last with 2.

If it increases the current sum, the element is included Thus we use a greedy strategy here

Formally,

Let X[i] represent the sequence 2, 3, 1
Let M[j] store the index k of the smallest value X[k] so that there is an increasing subsequence of length j ending at X[k] on the range k <=i and j <=k <= i.  j represents the length of the increasing subsequence and k represents the index of termination.
and Let P[k] store the index predecessor of X[k]
The longest Increasing subsequence  at any given point is given by X [M [1]], X [M [2]], ... X [M [L]] and if there is an increasing subsequence at i then there is one at i-1 which is X [P [M[i]]] and between these two bounds we can do a logarithmic search for j <=k <= i
Therefore the steps are:
P = array of length N  - all initialized to zero
M = array of length N + 1 // pad on the left so that we can use zero based index.
L = 0
for i in range 0 to N-1:
      Binary search for the largest positive j <= L
      such that X[M[j]] < X[i]
      lo = 1
      hi = L
      Binary Search between lo and hi adjusts lo and hi
      After searching lo is 1 greater than the length of the longest prefix
      newL = lo
      The predecessor of X[i] is the last index of the subsequence of length newL-1
      P[i] = M[newL -1]
      M[newL] = i
      if newL > L:
          if we found a subsequence longer than L, update L
          L = newL

   // Reconstruct the longest increasing subsequence
S = array of length L
k = M[L]
for i in range L-1 to 0:
    S[i] = X[k]
     k = P[k]

return S

For the bridge problem, we find the longest increasing subsequence first for the north side and then for the south side of the river and take the smaller of the two.

#codingexercise
Double  GetNthRootProductAlternateTermRaisedPMinusQoverPDividedQ (Double [] A,Double  p, Double q)
{
If ( A== null) return 0;
Return A.NthRootProductAlternateTermRaisedPMinusQoverPDividedQ(p, q);
}