Given an array arr[] of N integers, the task is to print the subsequence from the given array with the maximum pairwise absolute difference of adjacent elements. If multiple such subsequences exist, then print the subsequence with the smallest length.
Examples:
Input: arr[] = {1, 2, 4, 3, 5}
Output: 1 4 3 5
Explanation:
For the subsequence {1, 4, 3, 5},
The absolute difference between adjacent pair is |1 – 4| + |4 – 3| + |3 – 5| = 6, which is the maximum possible absolute difference.Input: arr[] = {1, 2, 5, 6, 3, 4}
Output: {1, 6, 4}
Explanation:
For the subsequence {1, 6, 4},
The absolute difference between adjacent pair is |1 – 6| + |6 – 4| = 7, which is the maximum possible absolute difference.
Approach: For the subsequence with the maximum absolute difference, below are the steps:
- Create the new array(say ans[]) to store all the elements of the required subsequence.
- Insert the first element of the array arr[].
- Find all the local minima and maxima of the array excluding the first and last element of the array and insert, in the array ans[].
- Insert the last element of the array arr[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the subsequence// with maximum absolute differencevoid getSubsequence(vector<int> ar){ int N = ar.size(); // To store the resultant subsequence vector<int> ans; // First element should be included // in the subsequence ans.push_back(ar[0]); // Traverse the given array arr[] for (int i = 1; i < N - 1; i++) { // If current element is greater // than the previous element if (ar[i] > ar[i - 1]) { // If the current element is // not the local maxima // then continue if (i < N - 1 && ar[i] <= ar[i + 1]) { continue; } // Else push it in subsequence else { ans.push_back(ar[i]); } } // If the current element is less // then the previous element else { // If the current element is // not the local minima // then continue if (i < N - 1 && ar[i + 1] < ar[i]) { continue; } // Else push it in subsequence else { ans.push_back(ar[i]); } } } // Last element should also be // included in subsequence ans.push_back(ar[N - 1]); // Print the element for (auto& it : ans) cout << it << ' ';}// Driver Codeint main(){ // Given array vector<int> arr = { 1, 2, 4, 3, 5 }; // Function Call getSubsequence(arr);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the subsequence// with maximum absolute differencestatic void getSubsequence(int []ar){ int N = ar.length; // To store the resultant subsequence Vector<Integer> ans = new Vector<Integer>(); // First element should be included // in the subsequence ans.add(ar[0]); // Traverse the given array arr[] for(int i = 1; i < N - 1; i++) { // If current element is greater // than the previous element if (ar[i] > ar[i - 1]) { // If the current element is // not the local maxima // then continue if (i < N - 1 && ar[i] <= ar[i + 1]) { continue; } // Else push it in subsequence else { ans.add(ar[i]); } } // If the current element is less // then the previous element else { // If the current element is // not the local minima // then continue if (i < N - 1 && ar[i + 1] < ar[i]) { continue; } // Else push it in subsequence else { ans.add(ar[i]); } } } // Last element should also be // included in subsequence ans.add(ar[N - 1]); // Print the element for(int it : ans) System.out.print(it + " ");}// Driver Codepublic static void main(String[] args){ // Given array int []arr = { 1, 2, 4, 3, 5 }; // Function Call getSubsequence(arr);}}// This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach# Function to find the subsequence# with maximum absolute differencedef getSubsequence(ar): N = len(ar) # To store the resultant subsequence ans = [] # First element should be included # in the subsequence ans.append(ar[0]) # Traverse the given array arr[] for i in range(1, N - 1): # If current element is greater # than the previous element if (ar[i] > ar[i - 1]): # If the current element is # not the local maxima # then continue if(i < N - 1 and ar[i] <= ar[i + 1]): continue # Else push it in subsequence else: ans.append(ar[i]) # If the current element is less # then the previous element else: # If the current element is # not the local minima # then continue if (i < N - 1 and ar[i + 1] < ar[i]): continue # Else push it in subsequence else: ans.append(ar[i]) # Last element should also be # included in subsequence ans.append(ar[N - 1]) # Print the element for it in ans: print(it, end = " ")# Driver Codeif __name__ == '__main__': # Given array arr = [ 1, 2, 4, 3, 5 ] # Function Call getSubsequence(arr)# This code is contributed by Shivam Singh |
C#
// C# program for the above approach using System;using System.Collections.Generic;class GFG{ // Function to find the subsequence // with maximum absolute difference static void getSubsequence(int []ar) { int N = ar.Length; // To store the resultant subsequence List<int> ans = new List<int>(); // First element should be included // in the subsequence ans.Add(ar[0]); // Traverse the given array []arr for(int i = 1; i < N - 1; i++) { // If current element is greater // than the previous element if (ar[i] > ar[i - 1]) { // If the current element is // not the local maxima // then continue if (i < N - 1 && ar[i] <= ar[i + 1]) { continue; } // Else push it in subsequence else { ans.Add(ar[i]); } } // If the current element is less // then the previous element else { // If the current element is // not the local minima // then continue if (i < N - 1 && ar[i + 1] < ar[i]) { continue; } // Else push it in subsequence else { ans.Add(ar[i]); } } } // Last element should also be // included in subsequence ans.Add(ar[N - 1]); // Print the element foreach(int it in ans) Console.Write(it + " "); } // Driver Code public static void Main(String[] args) { // Given array int []arr = { 1, 2, 4, 3, 5 }; // Function Call getSubsequence(arr); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program for the above approach // Function to find the subsequence // with maximum absolute difference function getSubsequence(ar) { let N = ar.length; // To store the resultant subsequence let ans = []; // First element should be included // in the subsequence ans.push(ar[0]); // Traverse the given array arr[] for(let i = 1; i < N - 1; i++) { // If current element is greater // than the previous element if (ar[i] > ar[i - 1]) { // If the current element is // not the local maxima // then continue if (i < N - 1 && ar[i] <= ar[i + 1]) { continue; } // Else push it in subsequence else { ans.push(ar[i]); } } // If the current element is less // then the previous element else { // If the current element is // not the local minima // then continue if (i < N - 1 && ar[i + 1] < ar[i]) { continue; } // Else push it in subsequence else { ans.push(ar[i]); } } } // Last element should also be // included in subsequence ans.push(ar[N - 1]); // Print the element for(let it = 0; it < ans.length; it++) document.write(ans[it] + " "); } // Given array let arr = [ 1, 2, 4, 3, 5 ]; // Function Call getSubsequence(arr);</script> |
Output:
1 4 3 5
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
