Given an array arr[] of size N. The task is to maximize the count of subarrays that contain both the minimum and maximum elements of the array by deleting at most one element from the array.
Examples:
Input: arr[] = {7, 2, 5, 4, 3, 1}
Output: 4
Explanation:
Delete 1 from the array then resultant array will be {7, 2, 5, 4, 3}. So the number of subarrays which contain maximum element 7 and minimum element 2 will be 4 {[7, 2], [7, 2, 5], [7, 2, 5, 4], [7, 2, 5, 4, 3]}
Input: arr[] = {9, 9, 8, 9, 8, 9, 9, 8, 9, 8}
Output: 43
Naive Approach: The simplest approach is to delete every element and then count the number of subarrays having the minimum and maximum element of the resultant array.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: This approach is based on the observation that deletion of elements other than the maximum or minimum element never maximizes the overall result. Below are the steps:
- Initialize the overall result with INT_MIN.
- Create a function say proc which returns the number of subarrays containing the smallest and the largest element of the array.
- To calculate the number of subarrays find the starting and ending index of the subarray using two pointers approach:
- Initialize the smallest and the largest element say low and high with the last element of the array.
- Initialize two pointers p1 and p2 with the last index of array which stores the location of low and high.
- Now, iterate over the array and check if the current element is less than low, then update p1.
- If the current element is more than high, then update p2.
- At each step, update the maximum number of subarrays.
- Now, calculate the number of subarrays in the following three cases:
- Without removing any element
- After removing the largest element
- After removing the smallest element.
- Without removing any element
- Take the maximum of all three cases.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Returns the count of subarrays// which contains both the maximum and// minimum elements in the given vectorlong long proc(vector<int> &v) { long long int n = v.size(); // Initialize the low and // high of array int low = v[n - 1], high = v[n - 1]; long long int p1 = n, p2 = n; long long ans = 0; for (int i = n - 1; i >= 0; i--) { int x = v[i]; // If current element is // less than least element if (x < low) { low = x; ans = 0; } // If current element is // more than highest element else if (x > high) { high = x; ans = 0; } // If current element is // equal to low or high // then update the pointers if (x == low) p1 = i; if (x == high) p2 = i; // Update number of subarrays ans += n - max(p1, p2); } // Return the result return ans; } // Function to find the maximum // count of subarrayslong long subarray(vector<int>& v){ long long int n=v.size(); if(n<=1) return n; long long ans=proc(v); int low=v[0],pos_low=0,high=v[0],pos_high=0; // Iterate the array to find // the maximum and minimum element for (int i = 1; i < n; i++) { int x = v[i]; if (x < low) { low = x; pos_low = i; } else if (x > high) { high = x; pos_high = i; } } // Vector after removing the // minimum element vector<int>u; // Using assignment operator to copy one // vector to other u=v; u.erase(u.begin()+pos_low); ans=max(ans,proc(u)); // Vector after removing the // maximum element vector<int>w; w=v; w.erase(w.begin()+pos_high); return max(ans,proc(w)); }// Driver Codeint main(){ // Given array vector<int>v; v.push_back(7); v.push_back(2); v.push_back(5); v.push_back(4); v.push_back(3); v.push_back(1); // Function Call cout<<subarray(v)<<endl; return 0;}// This code is contributed by dwivediyash |
Java
// Java implementation of the above approachimport java.util.*;import java.lang.*;class GFG { // Function to find the maximum // count of subarrays static long subarray(List<Integer> v) { int n = v.size(); if (n <= 1) return n; long ans = proc(v); int low = v.get(0), pos_low = 0; int high = v.get(0), pos_high = 0; // Iterate the array to find // the maximum and minimum element for (int i = 1; i < n; i++) { int x = v.get(i); if (x < low) { low = x; pos_low = i; } else if (x > high) { high = x; pos_high = i; } } // List after removing the // minimum element List<Integer> u = new ArrayList<>( Collections.nCopies(n, 0)); Collections.copy(u, v); u.remove(pos_low); ans = Math.max(ans, proc(u)); // List after removing the // maximum element List<Integer> w = new ArrayList<>( Collections.nCopies(n, 0)); Collections.copy(w, v); w.remove(pos_high); return Math.max(ans, proc(w)); } // Returns the count of subarrays // which contains both the maximum and // minimum elements in the given list static long proc(List<Integer> v) { int n = v.size(); // Initialize the low and // high of array int low = v.get(n - 1), high = v.get(n - 1); int p1 = n, p2 = n; long ans = 0; for (int i = n - 1; i >= 0; i--) { int x = v.get(i); // If current element is // less than least element if (x < low) { low = x; ans = 0; } // If current element is // more than highest element else if (x > high) { high = x; ans = 0; } // If current element is // equal to low or high // then update the pointers if (x == low) p1 = i; if (x == high) p2 = i; // Update number of subarrays ans += n - Math.max(p1, p2); } // Return the result return ans; } // Driver Code public static void main(String[] args) { // Given array List<Integer> arr = Arrays.asList(7, 2, 5, 4, 3, 1); // Function Call System.out.println(subarray(arr)); }} |
Python3
# Python program for the above approach# Returns the count of subarrays# which contains both the maximum and# minimum elements in the given vectordef proc(v): n = len(v); # Initialize the low and # high of array low = v[n - 1] high = v[n - 1] p1 = n p2 = n; ans = 0; for i in range(n - 1, -1, -1): x = v[i]; # If current element is # less than least element if (x < low): low = x; ans = 0; # If current element is # more than highest element elif (x > high): high = x; ans = 0; # If current element is # equal to low or high # then update the pointers if (x == low): p1 = i; if (x == high): p2 = i; # Update number of subarrays ans += n - max(p1, p2); # Return the result return ans;# Function to find the maximum# count of subarraysdef subarray(v): n = len(v); if (n <= 1): return n; ans = proc(v); low = v[0] pos_low = 0 high = v[0] pos_high = 0 # Iterate the array to find # the maximum and minimum element for i in range(1, n): x = v[i]; if (x < low): low = x; pos_low = i; elif (x > high): high = x; pos_high = i; # Vector after removing the # minimum element u = v[:]; # Using assignment operator to copy one # vector to other del u[pos_low]; ans = max(ans, proc(u)); # Vector after removing the # maximum element w = v[:]; del w[pos_high]; return max(ans, proc(w));# Driver Code# Given arrayv = [];v.append(7);v.append(2);v.append(5);v.append(4);v.append(3);v.append(1);# Function Callprint(subarray(v));# This code is contributed by gfgking |
C#
// C# program to implement above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // Function to find the maximum // count of subarrays static long subarray(List<int> v) { int n = v.Count; if (n <= 1){ return n; } long ans = proc(v); int low = v[0], pos_low = 0; int high = v[0], pos_high = 0; // Iterate the array to find // the maximum and minimum element for (int i = 1 ; i < n ; i++) { int x = v[i]; if (x < low) { low = x; pos_low = i; } else if (x > high) { high = x; pos_high = i; } } // List after removing the // minimum element List<int> u = new List<int>(); for(int i = 0 ; i < n ; i++){ u.Add(0); } u = new List<int>(v); u.Remove(v[pos_low]); ans = Math.Max(ans, proc(u)); // List after removing the // maximum element List<int> w = new List<int>(); for(int i = 0 ; i < n ; i++){ w.Add(0); } w = new List<int>(v); w.Remove(v[pos_high]); return Math.Max(ans, proc(w)); } // Returns the count of subarrays // which contains both the maximum and // minimum elements in the given list static long proc(List<int> v) { int n = v.Count; // Initialize the low and // high of array int low = v[n-1], high = v[n-1]; int p1 = n, p2 = n; long ans = 0; for (int i = n - 1; i >= 0; i--) { int x = v[i]; // If current element is // less than least element if (x < low) { low = x; ans = 0; } // If current element is // more than highest element else if (x > high) { high = x; ans = 0; } // If current element is // equal to low or high // then update the pointers if (x == low) p1 = i; if (x == high) p2 = i; // Update number of subarrays ans += n - Math.Max(p1, p2); } // Return the result return ans; } public static void Main(string[] args){ // Given array List<int> arr = new List<int>{ 7, 2, 5, 4, 3, 1 }; // Function Call Console.WriteLine(subarray(arr)); }}// This code is contributed by subhamgoyal2014. |
Javascript
<script>// Javascript program for the above approach// Returns the count of subarrays// which contains both the maximum and// minimum elements in the given vectorfunction proc(v){ let n = v.length; // Initialize the low and // high of array let low = v[n - 1], high = v[n - 1]; let p1 = n, p2 = n; let ans = 0; for (let i = n - 1; i >= 0; i--) { let x = v[i]; // If current element is // less than least element if (x < low) { low = x; ans = 0; } // If current element is // more than highest element else if (x > high) { high = x; ans = 0; } // If current element is // equal to low or high // then update the pointers if (x == low) p1 = i; if (x == high) p2 = i; // Update number of subarrays ans += n - Math.max(p1, p2); } // Return the result return ans;}// Function to find the maximum// count of subarraysfunction subarray(v) { let n = v.length; if (n <= 1) { return n; } let ans = proc(v); let low = v[0], pos_low = 0, high = v[0], pos_high = 0; // Iterate the array to find // the maximum and minimum element for (let i = 1; i < n; i++) { let x = v[i]; if (x < low) { low = x; pos_low = i; } else if (x > high) { high = x; pos_high = i; } } // Vector after removing the // minimum element let u = [...v]; // Using assignment operator to copy one // vector to other u.splice(pos_low, 1); ans = Math.max(ans, proc(u)); // Vector after removing the // maximum element let w = [...v]; w.splice(pos_high, 1); return Math.max(ans, proc(w));}// Driver Code// Given arraylet v = [];v.push(7);v.push(2);v.push(5);v.push(4);v.push(3);v.push(1);// Function Calldocument.write(subarray(v));// This code is contributed by gfgking</script> |
Output
4
Time Complexity: O(N)
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!
