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.
We are given an unsorted array. Our task is to find the length of longest subarray while we can discard at most m element.
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.
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]
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.
Using a 2D matrix is overwhelmingly complicated. So why not just expand subarray one by one.
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 = 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))
No comment yet