Longest subsequence with elements skipped

Published 7 months ago, last updated 7 months ago

This afternoon I encountered with an interesting problem on StackOverflow, which could be a follow up question of the classic Dynamic Programming problem Longest Increasing subsequence.

Problem

We are given an unsorted array. Our task is to find the length of longest subarray while we can discard at most m element.

Difference between classic LIS and this problem

In classic LIS problem. We are looking for a subsequence. So the distance between elements don't matter. So when we process a new element, we look back for all previous element and length so that we could append current element at the end. But in this problem, we are looking for a subarray with some of elements discarded.

Example:

A = [1,4,3,2,5,6,7]
subsequence = [1,2,5,6,7]
if m == 1
subarray = [2,5,6,7]
if m == 2
subarray = [1,2,5,6,7]

My initial idea

As the answer below that question suggest, it's easy for one to come up with the idea using a 2D matrix, and each entry dp[i][j] represent by the end of index j while discarding i elements at most, the length of longest subrange we can get. It sounds reasonable and seems easy to implement. But it does have some issue while implementing, here is an example.

a = [0,4,5,1,3,2,6,7,8,9]

when we encounter 3, we can extends subarray by removing 3 and reach 1. Next round, we are unable to extend because 4 is larger than 1 (even we discard 5). The problem is, when we want to discard 4 and 5 to let 0 be the first element in subarray, we don't know how many elements left we can discard.

Expanding subarray one by one

Using a 2D matrix is overwhelmingly complicated. So why not just expand subarray one by one.

  1. set up a dp array where dp[i] means the longest subarray ends at i
  2. Expand subarray from i - dp[i] towards 0 as much as we can.
  3. Record the maximum length.

Here are codes with comment:

def longest_increase_subrange_with_discard(_list, _m):
    """
    This method accept a list of number and a number of elements
    we can skip.
    :param _list: an unsorted array.
    :param _m: number of element we can discard.
    :return: longest subrange of this array.
    """
    _n = len(_list)
    dp = [0 for _ in range(_n)]
    dp[0] = 1
    for i in range(1, _n):
        dp[i] = dp[i - 1] + 1 if _list[i] > _list[i - 1] else 1

    _max = 0
    for i, value in enumerate(dp):
        _max = max(_max, extend(i, value, _m, _list))
    return _max


def extend(index, length, _m, _list):
    """
    extend subarray towards array's head as much as we can.
    :param index: end index of sugrange
    :param length: initial length of subarray.
    :param _m: number of elements we can discard
    :param _list: input array.
    :return: length after extend.
    """
    _used = 0
    _start = index + 1 - length
    _pre = _start
    while _pre > 0 and _used <= _m:
        _pre -= 1
        if _list[_pre] >= _list[_start]:
            _used += 1
        else:
            _start = _pre
            length += 1
    return length



# number of input
T = int(input())
for _ in range(T):
    # input array
    _content = list(map(int, input().split()))
    # number of element to skip
    m = int(input())
    print(longest_increase_subrange_with_discard(_content, m))


Comments

    No comment yet



Leave your comment