Given an array arr[] of integers, if the differences between consecutive numbers alternate between positive and negative. More formally, if arr[i] – arr[i-1] has a different sign for all i from 1 to n-1, the subsequence is considered a zig-zag subsequence. Find out the length of the longest Zig-Zag subsequence of the given array.
Examples:
Input: arr[] = {1, 7, 4, 9, 2, 5}
Output: 6
Explanation: The entire sequence is a zig-zag sequence.Input: arr[] = {1, 17, 5, 10, 13, 15, 10, 5, 16, 8}
Output: 7
Explanation: The zig-zag subsequence is [1, 17, 10, 13, 10, 16, 8].
Approach: To solve the problem follow the below idea:
We can solve this problem using Dynamic Programming.
Follow the steps to solve the problem:
- Create two arrays, up and down, both of the same length as the input array. The up[i] array will store the length of the longest zig-zag subsequence ending at index i and having the last difference as positive. Similarly, the down[i] array will store the length of the longest zig-zag subsequence ending at index i and having the last difference as negative.
- Initialize both up and down arrays with values of 1 since any single element is a valid zig-zag subsequence of length 1.
- For each index i from 1 to n-1, compare the current element arr[i] with the previous element arr[i-1]. If arr[i] is greater, update up[i] using the maximum of up[i] and down[i-1] + 1, since the last difference is negative and now you have a positive difference.
- If arr[i] is smaller, update down[i] using the maximum of down[i] and up[i-1] + 1, since the last difference is positive and now you have a negative difference.
- The maximum value between up and down arrays at index n-1 will be the answer.
Below is the implementation of the above idea:
C++14
// C++ program to find longest Zig-Zag// subsequence in an array#include <algorithm>#include <iostream>#include <vector>using namespace std;int longestZigZag(vector<int>& arr){ int n = arr.size(); vector<int> up(n, 1); vector<int> down(n, 1); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (arr[i] > arr[j]) { // up[i] array will store the // length of the longest zig-zag // subsequence ending at index i up[i] = max(up[i], down[j] + 1); } else if (arr[i] < arr[j]) { // down[i] array will store the // length of the longest zig-zag // subsequence ending at index i down[i] = max(down[i], up[j] + 1); } } } return max(up[n - 1], down[n - 1]);}// Drivers codeint main(){ vector<int> arr = { 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }; // Function Call cout << longestZigZag(arr) << endl; return 0;} |
Java
// Java program to find longest// Zig-Zag subsequence in an arraypublic class GFG { // Function to return longest // Zig-Zag subsequence length public static int longestZigZag(int[] arr) { int n = arr.length; int[] up = new int[n]; int[] down = new int[n]; //initialize both up and down arrays with values of 1 for (int i = 0; i < n; i++) { up[i] = 1; down[i] = 1; } for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (arr[i] > arr[j]) { // up[i] array will store the length of the longest zig-zag subsequence ending at index i up[i] = Math.max(up[i], down[j] + 1); } else if (arr[i] < arr[j]) { // down[i] array will store the length of the longest zig-zag subsequence ending at index i down[i] = Math.max(down[i], up[j] + 1); } } } return Math.max(up[n - 1], down[n - 1]); } public static void main(String[] args) { int[] arr = {1, 7, 4, 9, 2, 5}; System.out.println(longestZigZag(arr)); }}// This code is contributed by spbabaraheem |
Python3
# Python3 program to find longest# Zig-Zag subsequence in an arraydef longestZigZag(arr): n = len(arr) up = [1] * n down = [1] * n for i in range(1, n): for j in range(i): if arr[i] > arr[j]: # up[i] array will store the length of the longest zig-zag subsequence ending at index i up[i] = max(up[i], down[j] + 1) elif arr[i] < arr[j]: # down[i] array will store the length of the longest zig-zag subsequence ending at index i down[i] = max(down[i], up[j] + 1) return max(up[-1], down[-1])# Example usagearr = [1, 7, 4, 9, 2, 5]print(longestZigZag(arr)) # This code is contributed by spbabaraheem |
Output
7
Time Complexity: O(n2)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
