## Infosys Interview Question

Program Managers**Country:**India

**Interview Type:**Written Test

Its nothing but the longest increasing sub-sequence problem.

```
static int lis( int arr[], int n )
{
int result = 0;
int[] lis = new int[n];
for (int i = 0; i < n; i++ )
lis[i] = 1;
for (int i = 1; i < n; i++ )
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] &&
lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
for (int i = 0; i < n; i++ )
if (result < lis[i])
result = lis[i];
return n-result;
}
```

It is longest increasing subsequence problem.

This is a O(n^2) solution.

```
static int lis( int arr[], int n )
{
int result = 0;
int[] lis = new int[n];
for (int i = 0; i < n; i++ )
lis[i] = 1;
for (int i = 1; i < n; i++ )
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] &&
lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
for (int i = 0; i < n; i++ )
if (result < lis[i])
result = lis[i];
return result;
}
```

It is longest increasing subsequence problem.

This is a O(n^2) solution.

```
static int lis( int arr[], int n )
{
int result = 0;
int[] lis = new int[n];
for (int i = 0; i < n; i++ )
lis[i] = 1;
for (int i = 1; i < n; i++ )
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] &&
lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
for (int i = 0; i < n; i++ )
if (result < lis[i])
result = lis[i];
return result;
}
```

1. find the longest increasing subsequence(with little change) -> maxlen

- Anonymous May 17, 20182. finally substract the str.len - maxlen

Time Complexity -O(nlogn) and Space Complexity - O(n^2)