Flat Subsequence SOLUTION ACL CONTEST

Flat Subsequence SOLUTION

Problem Statement

You are given a sequence A1,A2,…,AN and an integer K.Print the maximum possible length of a sequence B that satisfies the following conditions:B is a (not necessarily continuous) subsequence of A.For each pair of adjacents elements of B, the absolute difference of the elements is at most K

Constraints

1

N

300

,

000

0

A

i

300

,

000

0

K

300

,

000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

 

N

 

K

 

A

1

 

A

2

 

:

 

A

N

 

Output

Print the answer.

 

Sample Input 1 

Copy

10 3

1

5

4

3

8

6

9

7

2

4

Sample Output 1 

Copy

7

For example, 

B

=

(

1

,

4

,

3

,

6

,

9

,

7

,

4

)

 satisfies the conditions.

 

It is a subsequence of 

A

=

(

1

,

5

,

4

,

3

,

8

,

6

,

9

,

7

,

2

,

4

)

.

All of the absolute differences between two adjacent elements (

|

1

4

|

,

|

4

3

|

,

|

3

6

|

,

|

6

9

|

,

|

9

7

|

,

|

7

4

|

) are at most 

K

=

3

.

Leave a Comment

close
error: Content is protected !!
Free Udemy Courses and Hacking Resources Join Us on TelegramClick Here
+