#3409

Longest Subsequence With Decreasing Adjacent Difference

medium · 16.6% accepted · 150 likes · top 1%

array · dynamic programming

⊣ practice⊣ open on leetcode ↗

Description

You are given an array of integers nums.

Your task is to find the length of the longest subsequence seq of nums, such that the absolute differences between consecutive elements form a non-increasing sequence of integers. In other words, for a subsequence seq0, seq1, seq2, ..., seqm of nums, |seq1 - seq0| >= |seq2 - seq1| >= ... >= |seqm - seqm - 1|.

Return the length of such a subsequence.

Solution