FastPrep
Problem · Array

Longest Sorted Adjacent-Difference Subsequence

Learn this problem
● MediumAtlassian logoAtlassianINTERNFULLTIMEOA

Problem statement

Select a subsequence, then sort its values. In the sorted result, every adjacent difference must be either 0 or 1. Return the maximum possible subsequence length.

Function

longestAdjacentDifferenceSubsequence(arr: int[]) → int

Examples

Example 1

arr = [4,2,1,3,2,3]return = 6

After sorting all values become [1,2,2,3,3,4], whose adjacent differences are 0 or 1.

Constraints

  • 1 <= arr.length <= 100000
  • Values fit in a signed 32-bit integer.

More Atlassian problems

drafts saved locally
public int longestAdjacentDifferenceSubsequence(int[] arr) {
  // Write your code here.
}
arr[4,2,1,3,2,3]
expected6
checking account