Minimizing and Maximizing longest Increasing Subsequence (LIS)
Given a string S of length n-1, consisting of characters ‘<‘ and ‘>’ only. The ith character is the comparison result between the ith element and the (i+1)th element of the sequence. If the ith character of the string is ‘<‘, then the ith element of the sequence is less than the (i+1)st element. If the ith character of the string is ‘>’, then the ith element of the sequence is greater than the (i+1)st element. The task is determine two sequences of size n, consisting of integers between 1 and n, such that longest increasing subsequence (LIS) of first sequence is minimum possible and LIS of second sequence is maximum possible.
Example:
Input: n = 3, S = <<
Output:
1 2 3
1 2 3Input: n = 7, S = >><>><
Output:
7 6 4 5 3 1 2
3 2 1 6 5 4 7
Approach:
The idea is to use greedy algorithms. The intuition behind the solution is to create two sequences based on the comparison results in the input string.
For the sequence with the minimum Longest Increasing Subsequence (LIS), the idea is to assign the largest numbers first to the elements that are greater than their next element. This ensures that the LIS is as small as possible because the larger numbers are placed first, making it harder to find an increasing subsequence.
For the sequence with the maximum LIS, the approach is to assign the smallest numbers first to the elements that are less than their next element. This ensures that the LIS is as large as possible because the smaller numbers are placed first, making it easier to find an increasing subsequence.
In both cases, the scans the string from left to right and assigns numbers in decreasing or increasing order based on the comparison results. This approach will ensures that the sequences are constructed in a way that minimizes and maximizes the LIS, respectively. The sequences are then printed out.
Steps:
- Initialize the number of test cases, the length of the string, and the indices. Also, initialize the string to hold the comparison results.
- First Sequence (Minimum LIS):
- Start with the maximum number and the first index.
- Scan the string from left to right.
- If it’s the last element or the current element is greater than the next, assign the numbers in decreasing order for minimum LIS.
- Update the last index to the next element.
- Print the sequence.
- Second Sequence (Maximum LIS):
- Start with the minimum number and the first index.
- Scan the string from left to right again.
- If it’s the last element or the current element is less than the next, assign the numbers in increasing order for maximum LIS.
- Update the last index to the next element.
- Print the sequence.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Define the maximum size of the array const int MAX_N = 200000; int ans[MAX_N + 5]; // Function to solve the problem void solve( int n, const string& s) { int i, j; // Start with the maximum number and the first index int num = n, last = 0; for (i = 0; i < n; i++) { // If it's the last element or the current element // is greater than the next if (i == n - 1 || s[i] == '>' ) { // Assign the numbers in decreasing order for // minimum LIS for (j = i; j >= last; j--) ans[j] = num--; last = i + 1; } } // Print the sequence for (i = 0; i < n; i++) cout << ans[i] << (i == n - 1 ? '\n' : ' ' ); // Start with the minimum number and the first index num = 1, last = 0; for (i = 0; i < n; i++) { // If it's the last element or the current element // is less than the next if (i == n - 1 || s[i] == '<' ) { // Assign the numbers in increasing order for // maximum LIS for (j = i; j >= last; j--) ans[j] = num++; last = i + 1; } } // Print the sequence for (i = 0; i < n; i++) cout << ans[i] << (i == n - 1 ? '\n' : ' ' ); } // Driver code int main() { int n = 3; string s = "<<" ; // Call the solve function with the input parameters solve(n, s); return 0; } |
Java
public class Solution { // Define the maximum size of the array static final int MAX_N = 200000 ; static int [] ans = new int [MAX_N + 5 ]; // Function to solve the problem public static void solve( int n, String s) { int i, j; // Start with the maximum number and the first index int num = n, last = 0 ; for (i = 0 ; i < n; i++) { // If it's the last element or the current element // is greater than the next if (i == n - 1 || s.charAt(i) == '>' ) { // Assign the numbers in decreasing order for // minimum LIS for (j = i; j >= last; j--) ans[j] = num--; last = i + 1 ; } } // Print the sequence for (i = 0 ; i < n; i++) System.out.print(ans[i] + (i == n - 1 ? "\n" : " " )); // Start with the minimum number and the first index num = 1 ; last = 0 ; for (i = 0 ; i < n; i++) { // If it's the last element or the current element // is less than the next if (i == n - 1 || s.charAt(i) == '<' ) { // Assign the numbers in increasing order for // maximum LIS for (j = i; j >= last; j--) ans[j] = num++; last = i + 1 ; } } // Print the sequence for (i = 0 ; i < n; i++) System.out.print(ans[i] + (i == n - 1 ? "\n" : " " )); } // Driver code public static void main(String[] args) { int n = 3 ; String s = "<<" ; // Call the solve function with the input parameters solve(n, s); } } // This code is contributed by rambabuguphka |
Python3
# Define the maximum size of the array MAX_N = 200000 ans = [ 0 ] * (MAX_N + 5 ) # Function to solve the problem def solve(n, s): global ans i, j = 0 , 0 # Start with the maximum number and the first index num, last = n, 0 for i in range (n): # If it's the last element or the current element # is greater than the next if i = = n - 1 or s[i] = = '>' : # Assign the numbers in decreasing order for # minimum LIS for j in range (i, last - 1 , - 1 ): ans[j] = num num - = 1 last = i + 1 # Print the sequence print ( * ans[:n]) # Start with the minimum number and the first index num, last = 1 , 0 for i in range (n): # If it's the last element or the current element # is less than the next if i = = n - 1 or s[i] = = '<' : # Assign the numbers in increasing order for # maximum LIS for j in range (i, last - 1 , - 1 ): ans[j] = num num + = 1 last = i + 1 # Print the sequence print ( * ans[:n]) # Driver code if __name__ = = "__main__" : n = 3 s = "<<" solve(n, s) |
C#
using System; class Program { // Define the maximum size of the array const int MAX_N = 200000; static int [] ans = new int [MAX_N + 5]; // Function to solve the problem static void Solve( int n, string s) { int i, j; // Start with the maximum number and the first index int num = n, last = 0; for (i = 0; i < n; i++) { // If it's the last element or the current element is greater than the next if (i == n - 1 || s[i] == '>' ) { // Assign the numbers in decreasing order for minimum LIS for (j = i; j >= last; j--) ans[j] = num--; last = i + 1; } } // Print the sequence for (i = 0; i < n; i++) Console.Write(ans[i] + (i == n - 1 ? "\n" : " " )); // Start with the minimum number and the first index num = 1; last = 0; for (i = 0; i < n; i++) { // If it's the last element or the current element is less than the next if (i == n - 1 || s[i] == '<' ) { // Assign the numbers in increasing order for maximum LIS for (j = i; j >= last; j--) ans[j] = num++; last = i + 1; } } // Print the sequence for (i = 0; i < n; i++) Console.Write(ans[i] + (i == n - 1 ? "\n" : " " )); } // Driver code static void Main( string [] args) { int n = 3; string s = "<<" ; // Call the Solve function with the input parameters Solve(n, s); } } // This code is contributed by SHIVAMGUPTA0987654321 |
Javascript
// Javascript Implementation // Function to solve the problem function solve(n, s) { let ans = new Array(n + 5).fill(0); // Start with the maximum number and the first index let num = n, last = 0; for (let i = 0; i < n; i++) { if (i === n - 1 || s[i] === '>' ) { for (let j = i; j >= last; j--) { ans[j] = num--; } last = i + 1; } } // Print the sequence console.log(ans.slice(0, n).join( " " )); // Reset for the next sequence num = 1; last = 0; for (let i = 0; i < n; i++) { if (i === n - 1 || s[i] === '<' ) { for (let j = i; j >= last; j--) { ans[j] = num++; } last = i + 1; } } // Print the sequence console.log(ans.slice(0, n).join( " " )); } // Driver code const n = 3; const s = '<<' ; // Call the solve function with the input parameters solve(n, s); // This code is contributed by Tapesh(tapeshdua420) |
1 2 3 1 2 3
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us