Given a sorted array arr[] of size N, the task is to find the length of the longest subarray and print the subarray such that the sum of the differences of the maximum element of the chosen subarray with all other elements of that same subarray is
≤ K.i.e. ∑(amax-ai) ≤ K, for that given subarray.
Examples:
Input: N = 5, arr[] = {1, 4, 5, 6, 10}, K = 4
Output: 3
4 5 6
Explanation: The subarray is having the difference (6-4)+(6-5)+(6-6)= 2+1+0=3 which is of the longest length.Input: N = 5, arr[] = {2, 4, 5, 10, 28}, K = 20
Output: 4
2 4 5 10
Explanation: The subarray is having the difference (10-2)+(10-4)+(10-5)+(10-10) = 8+6+5+0 = 19 which is of the longest length.
Approach: To solve the problem follow the below idea:
We can generate all the subarray and check the difference of the maximum element of the subarray with all other elements of that same subarray and keep updating the subarray with the maximum length
Follow the below steps to solve the problem:
- Iterate through the array by maintaining 2 pointers which denote the starting and ending point of that subarray
- Then Iterate through the chosen subarray and check whether the difference as stated above is ≤ K
- If our required condition matches, then we simply update our max answer.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to find the longest subarray// satisfying the given conditionvoid findLongestSubarray(int arr[], int n, int k){ // Initializing ans to the minimum // integer value int ans = INT_MIN; // Initializing the left and right // index of the subarray int l = 0; int r = n - 1; // Nested loop to iterate over all // possible subarrays for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int diff_sum = 0; // Loop to calculate the sum // of absolute differences for (int k = j; k >= i; k--) { diff_sum += abs(arr[j] - arr[k]); } // Checking if the sum of // absolute differences is // less than or equal to K if (diff_sum <= k) { // Updating ans and the // left and of right index // the subarray ans = max(ans, j - i + 1); if (ans == diff_sum) { l = i; r = j; } } } } // Printing the result cout << ans << endl; for (int i = l; i <= r; i++) { cout << arr[i] << " "; } cout << endl;}// Driver codeint main(){ // First array int arr1[] = { 1, 4, 5, 6, 10 }; int n = sizeof(arr1) / sizeof(int); int K = 4; // Function call findLongestSubarray(arr1, n, K); // Second array int arr2[] = { 2, 4, 5, 10, 28 }; K = 20; // Function call findLongestSubarray(arr2, n, K); return 0;} |
Java
import java.util.Arrays;class GFG { // Function to find the longest subarray // satisfying the given condition static void findLongestSubarray(int[] arr, int n, int k) { // Initializing ans to the minimum // integer value int ans = Integer.MIN_VALUE; // Initializing the left and right // index of the subarray int l = 0; int r = n - 1; // Nested loop to iterate over all // possible subarrays for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int diff_sum = 0; // Loop to calculate the sum // of absolute differences for (int p = j; p >= i; p--) { diff_sum += Math.abs(arr[j] - arr[p]); } // Checking if the sum of // absolute differences is // less than or equal to K if (diff_sum <= k) { // Updating ans and the // left and of right index // the subarray ans = Math.max(ans, j - i + 1); if (ans == diff_sum) { l = i; r = j; } } } } // Printing the result System.out.println(ans); for (int i = l; i <= r; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // Nikunj Sonigara public static void main(String[] args) { // First array int[] arr1 = { 1, 4, 5, 6, 10 }; int n = arr1.length; int K = 4; // Function call findLongestSubarray(arr1, n, K); // Second array int[] arr2 = { 2, 4, 5, 10, 28 }; K = 20; // Function call findLongestSubarray(arr2, n, K); }} |
Python3
#python code for the above approach:# Function to find the longest subarray satisfying # the given conditiondef find_longest_subarray(arr, n, k): # Initializing ans to the minimum integer value ans = float('-inf') # Initializing the left and right index of the subarray l = 0 r = n - 1 # Nested loop to iterate over all possible subarrays for i in range(n): for j in range(i, n): diff_sum = 0 # Loop to calculate the sum of absolute differences for x in range(j, i - 1, -1): diff_sum += abs(arr[j] - arr[x]) # Checking if the sum of absolute differences # is less than or equal to K if diff_sum <= k: # Updating ans and the left and right index # of the subarray ans = max(ans, j - i + 1) if ans == diff_sum: l = i r = j # Printing the result print(ans) for i in range(l, r + 1): print(arr[i], end=" ") print()# Driver codedef main(): # First array arr1 = [1, 4, 5, 6, 10] n = len(arr1) k = 4 # Function call find_longest_subarray(arr1, n, k) # Second array arr2 = [2, 4, 5, 10, 28] k = 20 # Function call find_longest_subarray(arr2, n, k)main() |
C#
using System;class Program{ // Function to find the longest subarray // satisfying the given condition static void FindLongestSubarray(int[] arr, int n, int k) { // Initializing ans to the minimum // integer value int ans = int.MinValue; // Initializing the left and right // index of the subarray int l = 0; int r = n - 1; // Nested loop to iterate over all // possible subarrays for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int diffSum = 0; for (int x = j; x >= i; x--) { diffSum += Math.Abs(arr[j] - arr[x]); } if (diffSum <= k) { ans = Math.Max(ans, j - i + 1); if (ans == diffSum) { l = i; r = j; } } } } // Printing the result Console.WriteLine(ans); for (int i = l; i <= r; i++) { Console.Write(arr[i] + " "); } Console.WriteLine(); } static void Main() { int[] arr1 = { 1, 4, 5, 6, 10 }; int n = arr1.Length; int k = 4; // function call FindLongestSubarray(arr1, n, k); int[] arr2 = { 2, 4, 5, 10, 28 }; k = 20; // function call FindLongestSubarray(arr2, n, k); }} |
Javascript
// Function to find the longest subarray// satisfying the given conditionfunction findLongestSubarray(arr, n, k) { // Initializing ans to the minimum // integer value let ans = Number.MIN_SAFE_INTEGER; // Initializing the left and right // index of the subarray let l = 0; let r = n - 1; // Nested loop to iterate over all // possible subarrays for (let i = 0; i < n; i++) { for (let j = i; j < n; j++) { let diff_sum = 0; for (let k = j; k >= i; k--) { diff_sum += Math.abs(arr[j] - arr[k]); } if (diff_sum <= k) { ans = Math.max(ans, j - i + 1); if (ans === diff_sum) { l = i; r = j; } } } } // Printing the result console.log(ans); for (let i = l; i <= r; i++) { console.log(arr[i] + " "); } console.log();}let arr1 = [1, 4, 5, 6, 10];let n = arr1.length;let K = 4;// Function callfindLongestSubarray(arr1, n, K);let arr2 = [2, 4, 5, 10, 28];let n2 = arr2.length;let K2 = 20;// Function callfindLongestSubarray(arr2, n2, K2); |
Output
3 4 5 6 4 2 4
Time Complexity: O(N3)
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!
