FastPrepLongest Increasing Subsequence With Bounded Adjacent Difference
Problem · Array

Longest Increasing Subsequence With Bounded Adjacent Difference

Learn this problem
● HardAmazon logoAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

Given a non-empty integer array arr and a non-negative integer k, return the maximum length of a subsequence that satisfies all of the following:

  • The selected values are strictly increasing.
  • The difference between every pair of consecutive selected values is at most k.
  • The selected values preserve their relative order in arr.

A subsequence may delete any number of elements without changing the order of the remaining elements.

Function

longestBoundedIncreasingSubsequence(arr: int[], k: int) → int

Examples

Example 1

arr = [7,1,4,5,8,8,10,6,7,7,7,8]k = 4return = 6

One longest valid subsequence is [1,4,5,6,7,8]. It preserves input order, every adjacent difference is at most 4, and its length is 6.

Example 2

arr = [3,1,2,6,10,11,4,5]k = 3return = 4

The subsequence [1,2,4,5] is strictly increasing, preserves input order, and has adjacent differences 1, 2, and 1.

Example 3

arr = [5,4,3,2,1]k = 2return = 1

No two values form a strictly increasing pair in subsequence order, so every valid longest subsequence contains one value.

Constraints

  • 1 <= arr.length <= 2 * 10^5
  • -10^9 <= arr[i] <= 10^9
  • 0 <= k <= 2 * 10^9

More Amazon problems

drafts saved locally
public int longestBoundedIncreasingSubsequence(int[] arr, int k) {
  // write your code here
}
arr[7,1,4,5,8,8,10,6,7,7,7,8]
k4
expected6
checking account