Longest Increasing Subsequence with Stack Constraint
Given a sequence of N integers, find the length of the longest subsequence such that each element in the subsequence is strictly greater than the previous element, and all elements of the subsequence can be placed into a set of stacks. A new element can be placed onto an empty stack, or onto a stack if it is strictly greater than the top element of that stack. Any element can be removed from the top of any stack. The goal is to find the longest subsequence that can be constructed and then deconstructed using these stack operations.
Input
First line: integer N. Second line: N space-separated integers a_1, a_2, ..., a_N.
Output
A single integer: the length of the longest such subsequence.
Constraints
1 <= N <= 200000. -10^9 <= a_i <= 10^9.
Example 1
7 2 5 3 7 11 8 9
5
The LIS is [2, 3, 7, 8, 9] (length 5). This subsequence can be formed using stacks. The patience sorting logic directly finds the LIS length. For input [2, 5, 3, 7, 11, 8, 9]: 1. 2: tops = [2] 2. 5: tops = [2, 5] 3. 3: tops = [2, 3] (replaces 5) 4. 7: tops = [2, 3, 7] 5. 11: tops = [2, 3, 7, 11] 6.
Example 2
8 3 1 4 1 5 9 2 6
4
The LIS is [1, 4, 5, 6] or [1, 4, 5, 9] or [1, 2, 6], all of length 4. Patience sorting for LIS: 1. 3: tops = [3] 2. 1: tops = [1] 3. 4: tops = [1, 4] 4. 1: tops = [1, 4] (1 doesn't replace anything, remains at index 0) 5. 5: tops = [1, 4, 5] 6. 9: tops = [1, 4, 5, 9] 7. 2: tops = [1, 2, 5, 9] (2 re
Hints
Similar problems
- Maximum Sum of Non-Overlapping Positive SubarraysMedium
- Maximum Sum of Non-Overlapping IntervalsHard
- Longest Increasing Subsequence on a PermutationHard
- Longest Alternating SubsequenceMedium
- Maximum Sum of Non-Adjacent SubarraysMedium
- Maximum Sum of Non-Overlapping SegmentsMedium
More topics: Greedy problems, Dynamic Programming problems, Stack problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
7 2 5 3 7 11 8 9
8 3 1 4 1 5 9 2 6