A learning app stores the difficulty level of each lesson completed by a student. The lesson levels appear in chronological order.

For the main task, the student wants to build a step-by-step learning progression. Each selected lesson after the first must be exactly one level harder than the previous selected lesson.

Return the length of the longest learning progression.

Class

LearningProgressPlanner

Main Method

longestStepByStepProgression

int longestStepByStepProgression(List<Integer> lessonLevels)

Parameters

• lessonLevels: The difficulty levels of the completed lessons in chronological order.

Returns

Return the greatest possible number of selected lessons such that every selected level is exactly 1 greater than the preceding selected level.

Follow-up Method

longestFlexibleProgression

int longestFlexibleProgression(List<Integer> lessonLevels, int maxLevelGap)

Parameters

• lessonLevels: The difficulty levels of the completed lessons in chronological order.
• maxLevelGap: The largest allowed increase between two consecutively selected lesson levels.

Returns

Return the greatest possible number of selected lessons such that the levels are strictly increasing and the increase between consecutive selected levels is at most maxLevelGap.

Selection Rules

• Selected lessons do not need to be next to each other in lessonLevels.
• Their original relative order must be preserved.
• A progression containing one lesson is always valid.

Constraints

• 1 ≤ lessonLevels.size() ≤ 100,000
• 1 ≤ lessonLevels.get(i) ≤ 100,000
• 1 ≤ maxLevelGap ≤ 100,000

Examples

Example 1

longestStepByStepProgression( lessonLevels = List.of(5, 2, 3, 8, 4, 6, 5))

Output: 4

Explanation: Select the levels [2, 3, 4, 5]. Each selected lesson is exactly one level harder than the previous selected lesson.

Example 2

longestStepByStepProgression( lessonLevels = List.of(9, 4, 6, 5, 7, 6, 8))

Output: 3

Explanation: One longest progression is [4, 5, 6]. Another is [6, 7, 8].

Example 3

longestStepByStepProgression( lessonLevels = List.of(3, 7, 11))

Output: 1

Explanation: No later lesson is exactly one level harder than an earlier lesson, so only one lesson can be selected.

Follow-up Example 1

longestFlexibleProgression( lessonLevels = List.of(10, 2, 5, 3, 8, 6, 9, 12), maxLevelGap = 3)

Output: 5

Explanation: One longest progression is [2, 5, 8, 9, 12]. Its increases are 3, 3, 1, and 3.

Follow-up Example 2

longestFlexibleProgression( lessonLevels = List.of(4, 12, 6, 9, 7, 10), maxLevelGap = 2)

Output: 3

Explanation: Select [4, 6, 7]. Its increases are 2 and 1.

Follow-up Example 3

longestFlexibleProgression( lessonLevels = List.of(30, 5, 18, 7), maxLevelGap = 20)

Output: 2

Explanation: The student may select either [5, 18] or [5, 7]. No valid progression can contain three lessons while preserving the original order.