Skip to content

3409. Longest Subsequence With Decreasing Adjacent Difference 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int longestSubsequence(vector<int>& nums) {
    const int mx = ranges::max(nums);
    // dp[num][diff] := the length of the longest subsequence ending in `num`
    // s.t. the last absolute difference between consecutive elements is `diff`
    vector<vector<int>> dp(mx + 1, vector<int>(mx + 1));

    for (const int num : nums) {
      for (int prev = 1; prev <= mx; ++prev) {
        const int diff = abs(num - prev);
        dp[num][diff] = max(dp[num][diff], dp[prev][diff] + 1);
      }
      // dp[num][diff] := max(dp[num][j]), where j >= diff
      for (int j = mx - 1; j >= 0; --j)
        dp[num][j] = max(dp[num][j], dp[num][j + 1]);
    }

    return ranges::max_element(dp, ranges::less{}, [](const vector<int>& row) {
      return row[0];
    })->at(0);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int longestSubsequence(int[] nums) {
    final int mx = Arrays.stream(nums).max().getAsInt();
    // dp[num][diff] := the length of the longest subsequence ending in `num`
    // s.t. the last absolute difference between consecutive elements is `diff`
    int[][] dp = new int[mx + 1][mx + 1];

    for (final int num : nums) {
      for (int prev = 1; prev <= mx; ++prev) {
        final int diff = Math.abs(num - prev);
        dp[num][diff] = Math.max(dp[num][diff], dp[prev][diff] + 1);
      }
      // dp[num][diff] := max(dp[num][j]), where j >= diff
      for (int j = mx - 1; j >= 0; --j)
        dp[num][j] = Math.max(dp[num][j], dp[num][j + 1]);
    }

    return Arrays.stream(dp).mapToInt(row -> row[0]).max().getAsInt();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def longestSubsequence(self, nums: list[int]) -> int:
    mx = max(nums)
    # dp[num][diff] := the length of the longest subsequence ending in `num`
    # s.t. the last absolute difference between consecutive elements is `diff`
    dp = [[0] * (mx + 1) for _ in range(mx + 1)]

    for num in nums:
      for prev in range(1, mx + 1):
        diff = abs(num - prev)
        dp[num][diff] = max(dp[num][diff], dp[prev][diff] + 1)
      # dp[num][diff] := max(dp[num][j]) for j >= diff
      for j in range(mx - 1, -1, -1):
        dp[num][j] = max(dp[num][j], dp[num][j + 1])

    return max(map(max, dp))