Streaming and Query Once Space Complexity of Longest Increasing Subsequence

Xin Li, Yu Zheng

Longest Increasing Subsequence (LIS) is a fundamental problem in combinatorics and computer science. Previously, there have been numerous works on both upper bounds and lower bound…