Alternating Sequence Length ā Problem Statement & Solution Guide
Problem Description
Given an array of integers signal, determine the length of the longest subsequence where the elements alternate between increasing and decreasing order.
Examples
Input
[1, 2, 3, 2, 1, 2, 3, 4, 3]
Output
5
Explanation: Step-by-step: with input [1, 2, 3, 2, 1, 2, 3, 4, 3], we first initialize variables i and j to 0. We then iterate through the array, incrementing i when the current element is greater than the previous one and incrementing j when the current element is less than the previous one. The maximum of i and j is the length of the longest alternating subsequence.
Input
[1, 3, 2, 4, 3]
Output
5
Explanation: Step-by-step: with input [1, 3, 2, 4, 3], we first initialize variables i and j to 0. We then iterate through the array, incrementing i when the current element is greater than the previous one and incrementing j when the current element is less than the previous one. The maximum of i and j is the length of the longest alternating subsequence.
Constraints
- 1 <= array length <= 1000
- -1000 <= each element in the array <= 1000
Optimal Approach & Strategy
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.
Brute Force Approach
The brute-force approach involves checking all possible subsequences of the given array and determining if they alternate between increasing and decreasing order. This approach has a time complexity of O(nĀ²) due to the nested loops. However, it is not efficient for large arrays.
Verified Code Solutions
function longestAlternatingSubsequence(signal) { let n = signal.length; if (n === 0) return 0; let increasing = new Array(n).fill(1); let decreasing = new Array(n).fill(1); for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (signal[i] > signal[j]) increasing[i] = Math.max(increasing[i], decreasing[j] + 1); if (signal[i] < signal[j]) decreasing[i] = Math.max(decreasing[i], increasing[j] + 1); if (signal[i] === signal[j]) { increasing[i] = Math.max(increasing[i], increasing[j]); decreasing[i] = Math.max(decreasing[i], decreasing[j]); } } } return Math.max(Math.max(...increasing), Math.max(...decreasing)); }class Solution {
public int longestAlternatingSubsequence(int[] signal) {
int n = signal.length;
if (n == 0) {
return 0;
}
int max_length = 1;
int i = 1;
int j = 1;
for (int k = 1; k < n; k++) {
if (signal[k] > signal[k - 1]) {
i = Math.max(i + 1, j + 1);
} else if (signal[k] < signal[k - 1]) {
j = Math.max(i + 1, j + 1);
}
max_length = Math.max(max_length, Math.max(i, j));
}
return max_length;
}
}def longestAlternatingSubsequence(signal):
n = len(signal)
if n == 0:
return 0
max_length = 1
i = 1
j = 1
for k in range(1, n):
if signal[k] > signal[k - 1]:
i = max(i + 1, j + 1)
elif signal[k] < signal[k - 1]:
j = max(i + 1, j + 1)
max_length = max(max_length, max(i, j))
return max_lengthfunction longestAlternatingSubsequence(signal) { let n = signal.length; if (n === 0) return 0; let increasing = new Array(n).fill(1); let decreasing = new Array(n).fill(1); for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (signal[i] > signal[j]) increasing[i] = Math.max(increasing[i], decreasing[j] + 1); if (signal[i] < signal[j]) decreasing[i] = Math.max(decreasing[i], increasing[j] + 1); if (signal[i] === signal[j]) { increasing[i] = Math.max(increasing[i], increasing[j]); decreasing[i] = Math.max(decreasing[i], decreasing[j]); } } } return Math.max(Math.max(...increasing), Math.max(...decreasing)); }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.