mediumDynamic ProgrammingPattern: Mixed
Longest Alternating Subsequence Solution
Problem Statement
You are given an array of integers, find the length of the longest subsequence where the difference between any two consecutive elements is either increasing or decreasing by at least 1.
Examples
Example 1:
Input:[1, 3, 2, 4, 5, 2, 3, 6]
Output:5
Explanation: One possible subsequence is [1, 3, 2, 4, 6] where the difference between consecutive elements is either increasing or decreasing by at least 1.
Example 2:
Input:[5, 4, 3, 2, 1]
Output:5
Explanation: The longest subsequence is the array itself where the difference between consecutive elements is decreasing by at least 1.
Example 3:
Input:[1, 2, 3, 4, 5]
Output:2
Explanation: The longest subsequence is either [1, 2] or [2, 3] or [3, 4] or [4, 5] where the difference between consecutive elements is increasing by at least 1.
Constraints
- 1 <= length of array <= 1000
- -1000 <= element of array <= 1000
Time: O(n^2) Space: O(n)
Analyze constraints and compute optimal solutions step-by-step.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.