Given two array of N integers arr[] and costArray[], representing removal cost associated with each element. The task is to find the subsequence from the given array of minimum cost such that the sum of the difference between adjacent elements is maximum. On removing each element, cost is incurred.
Examples:
Input: N = 3, arr[] = { 3, 2, 1 }, costArray[] = {0, 1, 0}
Output: 4, 1
Explanation:
There are 4 subsequences of length at least 2 :
[ 3, 2 ] which gives us | 3 – 2 | = 1
[ 3, 1 ] which gives us | 3 – 1 | = 2
[ 2, 1 ] which gives us | 2 – 1 | = 1
[ 3, 2, 1 ] which gives us | 3 – 2 | + | 2 – 1 | = 2
So the answer is either [ 3, 1 ] or [ 3, 2, 1 ] . Since we want the subsequence to be as short as possible, the answer is [ 3, 1 ]. Cost incurrent removing element 2 is 1.
So, the sum of the sequence is 4.
and the cost is 1.
Input: N = 4, arr[] = { 1, 3, 4, 2}, costArray[] = {0, 1, 0, 0}
Output: 7, 1
Naive Approach:
The naive approach is simply to check all the subsequences by generating them by recursion and it takes the complexity of O(2^N) which is very high complexity. And from them choose the subsequence which follows the above condition with maximum absolute sum and a minimum length as mentioned above.
Efficient Approach:
- We can observe the pattern, let us assume three numbers a, b, c such that a = L, b = L + 6, c = L + 10 (L is any integer here). If they are in a continuous pattern one after another eg a, b, c (such that a < b < c).
- Then
| b – a | + | c – b | = | a – c | = 10
- here we can remove the middle element to reduce the size of the original sequence.
- In this way, reducing the size of the array by removing a middle element from the sequence will not affect the sum and also reduce the length of the sequence.
- Stores all the removed elements in the set. Add the cost of removed elements. Finally, calculate the sum sequence by excluding removed elements.
- Then print the sum of elements of subsequence and cost incurred.
In this way, we reduce the exponential complexity O(2^N) to the linear complexity O(N).
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;void costOfSubsequence( int N, int arr[], int costArray[]){ int i, temp; // initializing cost=0 int cost = 0; // to store the removed // element set<int> removedElements; // this will store the sum // of the subsequence int ans = 0; // checking all the element // of the vector for (i = 1; i < (N - 1); i++) { // storing the value of // arr[i] in temp variable temp = arr[i]; // if the situation like // arr[i-1]<arr[i]<arr[i+1] or // arr[i-1]>arr[i]>arr[i+1] occur // remove arr[i] i.e, temp // from sequence if (((arr[i - 1] < temp) && (temp < arr[i + 1])) || ((arr[i - 1] > temp) && (temp > arr[i + 1]))) { // insert the element in the set // removedElements removedElements.insert(temp); } } for (i = 0; i < (N); i++) { // storing the value of // arr[i] in temp temp = arr[i]; // taking the element not // in removedElements if (!(removedElements.count(temp) > 0)) { // adding the value of elements // of subsequence ans += arr[i]; } else { // if we have to remove // the element then we // need to add the cost // associated with the // element cost += costArray[i]; } } // printing the sum of // the subsequence with // minimum length possible cout << ans << ", "; // printing the cost incurred // in creating subsequence cout << cost << endl;}// Driver codeint main(){ int N; N = 4; int arr[N] = { 1, 3, 4, 2 }; int costArray[N] = { 0, 1, 0, 0 }; // calling the function costOfSubsequence( N, arr, costArray); return 0;} |
Java
import java.util.*; class GFG{ public static void costOfSubsequence(int N, int[] arr, int[] costArray) { int i, temp; // Initializing cost=0 int cost = 0; // To store the removed // element Set<Integer> removedElements = new HashSet<Integer>(); // This will store the sum // of the subsequence int ans = 0; // Checking all the element // of the vector for(i = 1; i < (N - 1); i++) { // Storing the value of // arr[i] in temp variable temp = arr[i]; // If the situation like // arr[i-1]<arr[i]<arr[i+1] or // arr[i-1]>arr[i]>arr[i+1] occur // remove arr[i] i.e, temp // from sequence if (((arr[i - 1] < temp) && (temp < arr[i + 1])) || ((arr[i - 1] > temp) && (temp > arr[i + 1]))) { // Insert the element in the set // removedElements removedElements.add(temp); } } for(i = 0; i < (N); i++) { // Storing the value of // arr[i] in temp temp = arr[i]; // Taking the element not // in removedElements if (!(removedElements.contains(temp))) { // Adding the value of elements // of subsequence ans += arr[i]; } else { // If we have to remove // the element then we // need to add the cost // associated with the // element cost += costArray[i]; } } // Printing the sum of // the subsequence with // minimum length possible System.out.print(ans + ", "); // Printing the cost incurred // in creating subsequence System.out.print(cost);}// Driver codepublic static void main(String[] args){ int N; N = 4; int[] arr = { 1, 3, 4, 2 }; int[] costArray = { 0, 1, 0, 0 }; // Calling the function costOfSubsequence(N, arr, costArray); }}// This code is contributed by divyeshrabadiya07 |
Python3
def costOfSubsequence(N, arr, costArray): # Initializing cost=0 i, temp, cost = 0, 0, 0 # To store the removed # element removedElements = {''} # This will store the sum # of the subsequence ans = 0 # Checking all the element # of the vector for i in range(1, N - 1): # Storing the value of # arr[i] in temp variable temp = arr[i] # If the situation like # arr[i-1]<arr[i]<arr[i+1] or # arr[i-1]>arr[i]>arr[i+1] occur # remove arr[i] i.e, temp # from sequence if (((arr[i - 1] < temp) and (temp < arr[i + 1])) or ((arr[i - 1] > temp) and (temp > arr[i + 1]))) : # Insert the element in the set # removedElements removedElements.add(temp) for i in range(0, N): # Storing the value of # arr[i] in temp temp = arr[i] # Taking the element not # in removedElements if(temp not in removedElements): # Adding the value of elements # of subsequence ans = ans + arr[i] else: # If we have to remove # the element then we # need to add the cost # associated with the # element cost += costArray[i] # Printing the sum of # the subsequence with # minimum length possible print(ans, end = ", ") # Printing the cost incurred # in creating subsequence print(cost)# Driver codeN = 4arr = [ 1, 3, 4, 2 ]costArray = [ 0, 1, 0, 0 ]# Calling the functioncostOfSubsequence(N, arr, costArray)# This code is contributed by Sanjit_Prasad |
C#
using System;using System.Collections.Generic;class GFG{ public static void costOfSubsequence(int N, int[] arr, int[] costArray) { int i, temp; // Initializing cost=0 int cost = 0; // To store the removed // element HashSet<int> removedElements = new HashSet<int>(); // This will store the sum // of the subsequence int ans = 0; // Checking all the element // of the vector for(i = 1; i < (N - 1); i++) { // Storing the value of // arr[i] in temp variable temp = arr[i]; // If the situation like // arr[i-1]<arr[i]<arr[i+1] or // arr[i-1]>arr[i]>arr[i+1] occur // remove arr[i] i.e, temp // from sequence if (((arr[i - 1] < temp) && (temp < arr[i + 1])) || ((arr[i - 1] > temp) && (temp > arr[i + 1]))) { // Insert the element in the set // removedElements removedElements.Add(temp); } } for(i = 0; i < (N); i++) { // Storing the value of // arr[i] in temp temp = arr[i]; // Taking the element not // in removedElements if (!(removedElements.Contains(temp))) { // Adding the value of elements // of subsequence ans += arr[i]; } else { // If we have to remove // the element then we // need to add the cost // associated with the // element cost += costArray[i]; } } // Printing the sum of // the subsequence with // minimum length possible Console.Write(ans + ", "); // Printing the cost incurred // in creating subsequence Console.Write(cost);}// Driver codepublic static void Main(String[] args){ int N; N = 4; int[] arr = { 1, 3, 4, 2 }; int[] costArray = { 0, 1, 0, 0 }; // Calling the function costOfSubsequence(N, arr, costArray); }}// This code is contributed by Amit Katiyar |
Javascript
<script> function costOfSubsequence(N,arr,costArray) { let i, temp; // initializing cost=0 let cost = 0; // to store the removed // element let removedElements = new Set(); // this will store the sum // of the subsequence let ans = 0; // checking all the element // of the vector for (i = 1; i < (N - 1); i++) { // storing the value of // arr[i] in temp variable temp = arr[i]; // if the situation like // arr[i-1]<arr[i]<arr[i+1] or // arr[i-1]>arr[i]>arr[i+1] occur // remove arr[i] i.e, temp // from sequence if (((arr[i - 1] < temp) && (temp < arr[i + 1])) || ((arr[i - 1] > temp) && (temp > arr[i + 1]))) { // insert the element in the set // removedElements removedElements.add(temp); } } for (i = 0; i < (N); i++) { // storing the value of // arr[i] in temp temp = arr[i]; // taking the element not // in removedElements if (!removedElements.has(temp)) { // adding the value of elements // of subsequence ans += arr[i]; } else { // if we have to remove // the element then we // need to add the cost // associated with the // element cost += costArray[i]; } } // printing the sum of // the subsequence with // minimum length possible document.write(ans + ", "); // printing the cost incurred // in creating subsequence document.write(cost); } // Driver code let N; N = 4; let arr= [ 1, 3, 4, 2 ]; let costArray= [ 0, 1, 0, 0 ]; // calling the function costOfSubsequence(N, arr,costArray);</script> |
Output:
7, 1
Time Complexity: O(NlogN)
Auxiliary Space: O(N) because it uses extra space for set removedElements
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!
