1
$\begingroup$

I have a problem related to a common dynamic programming problem LIS. I got LIS function that takes arr as an input and returns the length of the longest increasing subsequence.

def LIS(arr):
    n = len(arr)

    # initialize LIS values for all indexes
    lis = [1]*n
 
    # Compute optimized LIS values in bottom up manner
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j]:
                if lis[i] < lis[j] + 1:
                    lis[i] = lis[j]+1
    
    # return the maximum of all LIS
    return max(lis)

Now my problem is to modify the given LIS function to check whether the longest increasing subsequence is unique. For example: arr = [2,6,5,7,9,1], it has LIS 4 and it has no unique solution because LIS could be {2,6,7,9} or {2,5,7,9}.

Here is my attempt to this question. Inside the main condition check in the above function, I checked if there are two or more values in lis which are less than the current pointer, then it is not unique. This worked for some examples but didn't work for all. So, I was wondering what is the actual condition to check the uniqueness in this situation? Any hint would be appreciated.

if arr[i] > arr[j]:
                if lis[i] < lis[j] + 1:
                    lis[i] = lis[j]+1
                if lis[j] == lis[j-1]:
                    unique = false
$\endgroup$

1 Answer 1

1
$\begingroup$

What you did is, eh, checking whether there is a unique increasing subsequence of some kind, not necessary of the longest length. For example, your algorithm will claim non-uniqueness when it is checking the element $9$ in the array $[8, 7, 9, 1, 2, 3]$. However, the unique LIS is $[1, 2, 3]$.

The goal is whether the longest increasing subsequence (LIS) is unique. For each current element during the loop, we can keep track of whether there is only one possible LIS that ends at the the current element. Then we will check whether the LIS (of the whole array) ends at only one index and whether the LIS ending there is unique.

def is_lis_unique(arr):
    arr.append(float('infinity'))  # the LIS must end at this last number.
    n = len(arr)

    # Length is 1 for all subsequences of single element.
    lis = [1] * n
    # `unique_lis[i]` will tell whether the LIS that ends at index `i` is unique.
    unique_lis = [True] * n

    # Compute LIS values in bottom up manner
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j]:
                if lis[i] < lis[j] + 1:
                    lis[i] = lis[j] + 1
                    unique_lis[i] = unique_lis[j]
                elif lis[i] == lis[j] + 1:
                    # Another LIS has been found!
                    unique_lis[i] = False

    return unique_lis[-1]

print(is_lis_unique(([3, 4, 5, 1, 2])         # True
print(is_lis_unique([8, 7, 9, 1, 2, 3]        # True
print(is_lis_unique([8, 7, 9, 1, 2, 4, 3]))   # False

The code above is a Pythonic implementation. A "number" that is greater than all numbers is appended to the given array so that the LIS must end at that number. This is a trick to simplify the code.


Exercise: Given an array of integers of length $n$, compute the number of increasing subsequences of the longest length efficiently.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.