Apply For Jobs
Get Hiring UpdatesQuestion 2 – Special LIS
Special LIS
Here, in this page we will discuss one of the problem Special LIS that was asked in InfyTQ Advance Coding Section. We will discuss the problem description along with function description, Test Cases along with there explanation.
You will find the solution of the problem in different programming language.
Special LIS Problem statement-:
Given an array of N integers. Find the length of the longest increasing subsequence such that the difference between adjacent elements of the longest increasing subsequence is also increasing.
Note: It’s not required that the sequence should have strictly increasing numbers and the differences are also not required to be strictly increasing.
Ex: [1,2,3,4,5]. The longest increasing subsequence will be [1,2,4,5] but the difference array in this case is [1,2,1] which is not increasing. If we consider [1,2,4] or [1,2,5] then the numbers as well as the differences are in increasing order.
Function Description:
Complete the specialLIS function in the editor below. It has the following parameter(s):
Parameters:
| Name | Type | Type |
|---|---|---|
| size | Integer | size of array |
| arr | Integer array | array |
Return:
The function must return an INTEGER denoting the length of the longest increasing sub sequence with increasing differences.
Constraints:
- 1 <= size <= 500
- 1 <= arr[i] <= 10^5
Input Format:
- The first line contains integer, size, denoting the size of the array.
- Each line i of the size subsequent lines (where 0 <= i < size) contains an integer describing the ith elements of the array.
Sample Cases
- Sample Input 1
5
1
2
3
4
5
- Sample Output 1
5
#include <bits/stdc++.h>
using namespace std;
int n;
map<int,map<int,map<int,map<int,int>>>> m;
int fun(int i,int le,int d,int i1,vector<int> a)
{
if(m[i][le][d][i1]) return m[i][le][d][i1];
if(i==n) return m[i][le][d][i1]=le;
if(le==0) return m[i][le][d][i1]=max(fun(i+1,1,0,i,a),fun(i+1,0,0,i+1,a));
if(a[i]-a[i1]>=d) return m[i][le][d][i1]=max(fun(i+1,le+1,a[i]-a[i1],i,a),fun(i+1,le,d,i1,a));
return m[i][le][d][i1]=fun(i+1,le,d,i1,a);
}
int main()
{
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
cout<<fun(0,0,0,0,a);
}
n=int(input())
a=[]
for i in range(n):
a.append(int(input()))
dp=[[[[-2 for i in range(n+1)] for j in range((max(a)-min(a)+2))] for k in range(n+1)] for l in range(n+1)]
def answer(i,le,d,i1):
if dp[i][le][d][i1]!=-2:
return dp[i][le][d][i1]
if i==n:
dp[i][le][d][i1]=le
return dp[i][le][d][i1]
else:
if le==0:
dp[i][le][d][i1] = max(answer(i+1,1,0,i),answer(i+1,0,0,i+1))
return dp[i][le][d][i1]
else:
if (a[i]-a[i1])>=d:
dp[i][le][d][i1]= max(answer(i+1,le+1,(a[i]-a[i1]),i),answer(i+1,le,d,i1))
return dp[i][le][d][i1]
else:
dp[i][le][d][i1]= answer(i+1,le,d,i1)
return dp[i][le][d][i1]
print(answer(0,0,0,0))
import java.util.*;
public class Main{
public static void main(String[]args) {
Scanner sc = new Scanner(System.in);
System.out.println("enter the size of the array");
int n =sc.nextInt();
int[] arr = new int[n];
System.out.println("Elements are not of original array");
for (int i = 0;i<arr.length; i++) {
arr[i]=sc.nextInt();
}
System.out.println(lis(arr,n));
}
static int lis(int[] arr, int n)
{
int lis[] = new int[n];
int i, j, max = 0;
// Initialize LIS values for all indexes /
for (i = 0; i < n; i++)
lis[i] = 1;
// Compute optimized LIS values in
//bottom up manner /
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
//Pick maximum of all LIS values */
for (i = 0; i < n; i++)
if (max < lis[i])
max = lis[i];
return max;
}
}
Login/Signup to comment