mediumArraysPattern: Identifying patterns in arrays
Alternating Sequence Length Solution
Problem Statement
You are given an array of integers `signal`, determine the length of the longest subsequence where the elements alternate between increasing and decreasing order.
Examples
Example 1:
Input:[1, 2, 3, 2, 1, 2, 3, 4]
Output:6
Explanation: The longest alternating subsequence is [1, 2, 1, 2, 3, 2]
Example 2:
Input:[5, 4, 3, 2, 1]
Output:2
Explanation: The longest alternating subsequence is [5, 4] or any other pair of adjacent elements
Constraints
- 1 <= array length <= 1000
- -1000 <= each element in the array <= 1000
Time: O(n) Space: O(n)
The optimal approach involves using dynamic programming to store the lengths of the longest alternating subsequences ending at each position. This approach has a time complexity of O(n) and a space complexity of O(n), making it more efficient for large arrays.
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.