Součet min a max všech podpolí velikosti k.
Při daném poli kladných i záporných celých čísel je úkolem vypočítat součet minimálních a maximálních prvků všech dílčích polí o velikosti k.
Příklady:
Vstup : arr[] = {2 5 -1 7 -3 -1 -2}
K = 4
Výstup : 18
Vysvětlení : Podsoustavy velikosti 4 jsou:
{2 5 -1 7} min + max = -1 + 7 = 6
{5-1 7-3} min + max = -3 + 7 = 4
{-17-3-1} min + max = -3 + 7 = 4
{7-3-1-2} min + max = -3 + 7 = 4
Chybějící dílčí pole -
{2 -1 7 -3}
{2 7 -3 -1}
{2 -3 -1 -2}
{5 7 -3 -1}
{5 -3 -1 -2}
a několik dalších -- proč se o nich neuvažovalo?
Vezmeme-li v úvahu chybějící pole, výsledek přichází jako 27
Součet všech min a max = 6 + 4 + 4 + 4 = 18
Tento problém je hlavně rozšířením níže uvedeného problému.
Maximálně ze všech podpolí velikosti k
Naivní přístup:
C++Spusťte dvě cykly pro vygenerování všech podpolí a poté vyberte všechna podpole o velikosti k a najděte maximální a minimální hodnoty. Nakonec vraťte součet všech maximálních a minimálních prvků.
// C++ program to find sum of all minimum and maximum // elements Of Sub-array Size k. #include using namespace std ; // Returns sum of min and max element of all subarrays // of size k int SumOfKsubArray ( int arr [] int N int k ) { // To store final answer int sum = 0 ; // Find all subarray for ( int i = 0 ; i < N ; i ++ ) { // To store length of subarray int length = 0 ; for ( int j = i ; j < N ; j ++ ) { // Increment the length length ++ ; // When there is subarray of size k if ( length == k ) { // To store maximum and minimum element int maxi = INT_MIN ; int mini = INT_MAX ; for ( int m = i ; m <= j ; m ++ ) { // Find maximum and minimum element maxi = max ( maxi arr [ m ]); mini = min ( mini arr [ m ]); } // Add maximum and minimum element in sum sum += maxi + mini ; } } } return sum ; } // Driver program to test above functions int main () { int arr [] = { 2 5 -1 7 -3 -1 -2 }; int N = sizeof ( arr ) / sizeof ( arr [ 0 ]); int k = 4 ; cout < < SumOfKsubArray ( arr N k ); return 0 ; }
Java // Java program to find sum of all minimum and maximum // elements Of Sub-array Size k. import java.util.Arrays ; class GFG { // Returns sum of min and max element of all subarrays // of size k static int SumOfKsubArray ( int [] arr int N int k ) { // To store the final answer int sum = 0 ; // Find all subarrays for ( int i = 0 ; i < N ; i ++ ) { // To store the length of the subarray int length = 0 ; for ( int j = i ; j < N ; j ++ ) { // Increment the length length ++ ; // When there is a subarray of size k if ( length == k ) { // To store the maximum and minimum element int maxi = Integer . MIN_VALUE ; int mini = Integer . MAX_VALUE ; for ( int m = i ; m <= j ; m ++ ) { // Find the maximum and minimum element maxi = Math . max ( maxi arr [ m ] ); mini = Math . min ( mini arr [ m ] ); } // Add the maximum and minimum element to the sum sum += maxi + mini ; } } } return sum ; } // Driver program to test above functions public static void main ( String [] args ) { int [] arr = { 2 5 - 1 7 - 3 - 1 - 2 }; int N = arr . length ; int k = 4 ; System . out . println ( SumOfKsubArray ( arr N k )); } } //This code is contributed by Vishal Dhaygude
Python # Returns sum of min and max element of all subarrays # of size k def sum_of_k_subarray ( arr N k ): # To store final answer sum = 0 # Find all subarrays for i in range ( N ): # To store length of subarray length = 0 for j in range ( i N ): # Increment the length length += 1 # When there is a subarray of size k if length == k : # To store maximum and minimum element maxi = float ( '-inf' ) mini = float ( 'inf' ) for m in range ( i j + 1 ): # Find maximum and minimum element maxi = max ( maxi arr [ m ]) mini = min ( mini arr [ m ]) # Add maximum and minimum element to sum sum += maxi + mini return sum # Driver program to test above function def main (): arr = [ 2 5 - 1 7 - 3 - 1 - 2 ] N = len ( arr ) k = 4 print ( sum_of_k_subarray ( arr N k )) if __name__ == '__main__' : main ()
C# using System ; class Program { // Returns sum of min and max element of all subarrays // of size k static int SumOfKSubArray ( int [] arr int N int k ) { // To store the final answer int sum = 0 ; // Find all subarrays for ( int i = 0 ; i < N ; i ++ ) { // To store the length of subarray int length = 0 ; for ( int j = i ; j < N ; j ++ ) { // Increment the length length ++ ; // When there is a subarray of size k if ( length == k ) { // To store the maximum and minimum // element int maxi = int . MinValue ; int mini = int . MaxValue ; for ( int m = i ; m <= j ; m ++ ) { // Find maximum and minimum element maxi = Math . Max ( maxi arr [ m ]); mini = Math . Min ( mini arr [ m ]); } // Add maximum and minimum element in // sum sum += maxi + mini ; } } } return sum ; } // Driver program to test above functions static void Main () { int [] arr = { 2 5 - 1 7 - 3 - 1 - 2 }; int N = arr . Length ; int k = 4 ; Console . WriteLine ( SumOfKSubArray ( arr N k )); } }
JavaScript // JavaScript program to find sum of all minimum and maximum // elements of sub-array size k. // Returns sum of min and max element of all subarrays // of size k function SumOfKsubArray ( arr N k ) { // To store final answer let sum = 0 ; // Find all subarray for ( let i = 0 ; i < N ; i ++ ) { // To store length of subarray let length = 0 ; for ( let j = i ; j < N ; j ++ ) { // Increment the length length ++ ; // When there is subarray of size k if ( length === k ) { // To store maximum and minimum element let maxi = Number . MIN_SAFE_INTEGER ; let mini = Number . MAX_SAFE_INTEGER ; for ( let m = i ; m <= j ; m ++ ) { // Find maximum and minimum element maxi = Math . max ( maxi arr [ m ]); mini = Math . min ( mini arr [ m ]); } // Add maximum and minimum element in sum sum += maxi + mini ; } } } return sum ; } // Driver program to test above function const arr = [ 2 5 - 1 7 - 3 - 1 - 2 ]; const N = arr . length ; const k = 4 ; console . log ( SumOfKsubArray ( arr N k ));
Výstup
18
Časová náročnost: NA 2 *k) protože dvě smyčky pro nalezení celého podpole a jedna smyčka pro nalezení maxima a minima prvků v podpoli velikosti k
Pomocný prostor: O(1), protože nebylo použito žádné místo navíc
Metoda 2 (pomocí MultiSet):
Cílem je použít datovou strukturu Multiset a koncept posuvného okna.
- Nejprve vytvoříme a multiset páru {numberindex}, protože index by nám pomohl odstranit ith prvek a přesunout se do dalšího okna velikosti k .
- Zadruhé máme i a j což jsou zadní a přední ukazatel používané k údržbě okna.
- Projděte pole a vložte do vícemnožinového páru {numberindex} a také zkontrolujte velikost okna, jakmile se bude rovnat k začněte svůj primární cíl, tj. najít součet maximálních a minimálních prvků.
- Poté vymažte i-té číslo indexu ze sady a přesuňte i-tý ukazatel na další místo, tj. nové okno velikosti k.
Implementace:
C++ // C++ program to find sum of all minimum and maximum // elements Of Sub-array Size k. #include using namespace std ; // Returns sum of min and max element of all subarrays // of size k int SumOfKsubArray ( int arr [] int n int k ) { int sum = 0 ; // to store our final sum // multiset because nos. could be repeated // multiset pair is {numberindex} multiset < pair < int int > > ms ; int i = 0 ; // back pointer int j = 0 ; // front pointer while ( j < n && i < n ) { ms . insert ( { arr [ j ] j }); // inserting {numberindex} // front pointer - back pointer + 1 is for checking // window size int windowSize = j - i + 1 ; // Once they become equal start what we need to do if ( windowSize == k ) { // extracting first since set is always in // sorted ascending order int mini = ms . begin () -> first ; // extracting last element aka beginning from // last (numbers extraction) int maxi = ms . rbegin () -> first ; // adding summation of maximum & minimum element // of each subarray of k into final sum sum += ( maxi + mini ); // erasing the ith index element from set as it // won't appaer in next window of size k ms . erase ({ arr [ i ] i }); // increasing back pointer for next window of // size k; i ++ ; } j ++ ; // always increments front pointer } return sum ; } // Driver program to test above functions int main () { int arr [] = { 2 5 -1 7 -3 -1 -2 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int k = 4 ; cout < < SumOfKsubArray ( arr n k ); return 0 ; }
Výstup
18
Časová složitost: O(nlogk)
Pomocný prostor: O(k)
Metoda 3 (Efektivní pomocí Dequeue):
C++Cílem je použít datovou strukturu Dequeue a koncept posuvného okna. Vytvoříme dvě prázdné dvojité fronty velikosti k ('S' 'G'), které ukládají pouze indexy prvků aktuálního okna, které nejsou zbytečné. Prvek je k ničemu, pokud nemůže být maximem nebo minimem dalších podpolí.
// C++ program to find sum of all minimum and maximum // elements Of Sub-array Size k. #include using namespace std ; // Returns sum of min and max element of all subarrays // of size k int SumOfKsubArray ( int arr [] int n int k ) { int sum = 0 ; // Initialize result // The queue will store indexes of useful elements // in every window // In deque 'G' we maintain decreasing order of // values from front to rear // In deque 'S' we maintain increasing order of // values from front to rear deque < int > S ( k ) G ( k ); // Process first window of size K int i = 0 ; for ( i = 0 ; i < k ; i ++ ) { // Remove all previous greater elements // that are useless. while ( ( ! S . empty ()) && arr [ S . back ()] >= arr [ i ]) S . pop_back (); // Remove from rear // Remove all previous smaller that are elements // are useless. while ( ( ! G . empty ()) && arr [ G . back ()] <= arr [ i ]) G . pop_back (); // Remove from rear // Add current element at rear of both deque G . push_back ( i ); S . push_back ( i ); } // Process rest of the Array elements for ( ; i < n ; i ++ ) { // Element at the front of the deque 'G' & 'S' // is the largest and smallest // element of previous window respectively sum += arr [ S . front ()] + arr [ G . front ()]; // Remove all elements which are out of this // window if ( ! S . empty () && S . front () == i - k ) S . pop_front (); if ( ! G . empty () && G . front () == i - k ) G . pop_front (); // remove all previous greater element that are // useless while ( ( ! S . empty ()) && arr [ S . back ()] >= arr [ i ]) S . pop_back (); // Remove from rear // remove all previous smaller that are elements // are useless while ( ( ! G . empty ()) && arr [ G . back ()] <= arr [ i ]) G . pop_back (); // Remove from rear // Add current element at rear of both deque G . push_back ( i ); S . push_back ( i ); } // Sum of minimum and maximum element of last window sum += arr [ S . front ()] + arr [ G . front ()]; return sum ; } // Driver program to test above functions int main () { int arr [] = { 2 5 -1 7 -3 -1 -2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int k = 4 ; cout < < SumOfKsubArray ( arr n k ) ; return 0 ; }
Java // Java program to find sum of all minimum and maximum // elements Of Sub-array Size k. import java.util.Deque ; import java.util.LinkedList ; public class Geeks { // Returns sum of min and max element of all subarrays // of size k public static int SumOfKsubArray ( int arr [] int k ) { int sum = 0 ; // Initialize result // The queue will store indexes of useful elements // in every window // In deque 'G' we maintain decreasing order of // values from front to rear // In deque 'S' we maintain increasing order of // values from front to rear Deque < Integer > S = new LinkedList <> () G = new LinkedList <> (); // Process first window of size K int i = 0 ; for ( i = 0 ; i < k ; i ++ ) { // Remove all previous greater elements // that are useless. while ( ! S . isEmpty () && arr [ S . peekLast () ] >= arr [ i ] ) S . removeLast (); // Remove from rear // Remove all previous smaller that are elements // are useless. while ( ! G . isEmpty () && arr [ G . peekLast () ] <= arr [ i ] ) G . removeLast (); // Remove from rear // Add current element at rear of both deque G . addLast ( i ); S . addLast ( i ); } // Process rest of the Array elements for ( ; i < arr . length ; i ++ ) { // Element at the front of the deque 'G' & 'S' // is the largest and smallest // element of previous window respectively sum += arr [ S . peekFirst () ] + arr [ G . peekFirst () ] ; // Remove all elements which are out of this // window while ( ! S . isEmpty () && S . peekFirst () <= i - k ) S . removeFirst (); while ( ! G . isEmpty () && G . peekFirst () <= i - k ) G . removeFirst (); // remove all previous greater element that are // useless while ( ! S . isEmpty () && arr [ S . peekLast () ] >= arr [ i ] ) S . removeLast (); // Remove from rear // remove all previous smaller that are elements // are useless while ( ! G . isEmpty () && arr [ G . peekLast () ] <= arr [ i ] ) G . removeLast (); // Remove from rear // Add current element at rear of both deque G . addLast ( i ); S . addLast ( i ); } // Sum of minimum and maximum element of last window sum += arr [ S . peekFirst () ] + arr [ G . peekFirst () ] ; return sum ; } public static void main ( String args [] ) { int arr [] = { 2 5 - 1 7 - 3 - 1 - 2 } ; int k = 4 ; System . out . println ( SumOfKsubArray ( arr k )); } } //This code is contributed by Gaurav Tiwari
Python # Python3 program to find Sum of all minimum and maximum # elements Of Sub-array Size k. from collections import deque # Returns Sum of min and max element of all subarrays # of size k def SumOfKsubArray ( arr n k ): Sum = 0 # Initialize result # The queue will store indexes of useful elements # in every window # In deque 'G' we maintain decreasing order of # values from front to rear # In deque 'S' we maintain increasing order of # values from front to rear S = deque () G = deque () # Process first window of size K for i in range ( k ): # Remove all previous greater elements # that are useless. while ( len ( S ) > 0 and arr [ S [ - 1 ]] >= arr [ i ]): S . pop () # Remove from rear # Remove all previous smaller that are elements # are useless. while ( len ( G ) > 0 and arr [ G [ - 1 ]] <= arr [ i ]): G . pop () # Remove from rear # Add current element at rear of both deque G . append ( i ) S . append ( i ) # Process rest of the Array elements for i in range ( k n ): # Element at the front of the deque 'G' & 'S' # is the largest and smallest # element of previous window respectively Sum += arr [ S [ 0 ]] + arr [ G [ 0 ]] # Remove all elements which are out of this # window while ( len ( S ) > 0 and S [ 0 ] <= i - k ): S . popleft () while ( len ( G ) > 0 and G [ 0 ] <= i - k ): G . popleft () # remove all previous greater element that are # useless while ( len ( S ) > 0 and arr [ S [ - 1 ]] >= arr [ i ]): S . pop () # Remove from rear # remove all previous smaller that are elements # are useless while ( len ( G ) > 0 and arr [ G [ - 1 ]] <= arr [ i ]): G . pop () # Remove from rear # Add current element at rear of both deque G . append ( i ) S . append ( i ) # Sum of minimum and maximum element of last window Sum += arr [ S [ 0 ]] + arr [ G [ 0 ]] return Sum # Driver program to test above functions arr = [ 2 5 - 1 7 - 3 - 1 - 2 ] n = len ( arr ) k = 4 print ( SumOfKsubArray ( arr n k )) # This code is contributed by mohit kumar
C# // C# program to find sum of all minimum and maximum // elements Of Sub-array Size k. using System ; using System.Collections.Generic ; class Geeks { // Returns sum of min and max element of all subarrays // of size k public static int SumOfKsubArray ( int [] arr int k ) { int sum = 0 ; // Initialize result // The queue will store indexes of useful elements // in every window // In deque 'G' we maintain decreasing order of // values from front to rear // In deque 'S' we maintain increasing order of // values from front to rear List < int > S = new List < int > (); List < int > G = new List < int > (); // Process first window of size K int i = 0 ; for ( i = 0 ; i < k ; i ++ ) { // Remove all previous greater elements // that are useless. while ( S . Count != 0 && arr [ S [ S . Count - 1 ]] >= arr [ i ]) S . RemoveAt ( S . Count - 1 ); // Remove from rear // Remove all previous smaller that are elements // are useless. while ( G . Count != 0 && arr [ G [ G . Count - 1 ]] <= arr [ i ]) G . RemoveAt ( G . Count - 1 ); // Remove from rear // Add current element at rear of both deque G . Add ( i ); S . Add ( i ); } // Process rest of the Array elements for ( ; i < arr . Length ; i ++ ) { // Element at the front of the deque 'G' & 'S' // is the largest and smallest // element of previous window respectively sum += arr [ S [ 0 ]] + arr [ G [ 0 ]]; // Remove all elements which are out of this // window while ( S . Count != 0 && S [ 0 ] <= i - k ) S . RemoveAt ( 0 ); while ( G . Count != 0 && G [ 0 ] <= i - k ) G . RemoveAt ( 0 ); // remove all previous greater element that are // useless while ( S . Count != 0 && arr [ S [ S . Count - 1 ]] >= arr [ i ]) S . RemoveAt ( S . Count - 1 ); // Remove from rear // remove all previous smaller that are elements // are useless while ( G . Count != 0 && arr [ G [ G . Count - 1 ]] <= arr [ i ]) G . RemoveAt ( G . Count - 1 ); // Remove from rear // Add current element at rear of both deque G . Add ( i ); S . Add ( i ); } // Sum of minimum and maximum element of last window sum += arr [ S [ 0 ]] + arr [ G [ 0 ]]; return sum ; } // Driver code public static void Main ( String [] args ) { int [] arr = { 2 5 - 1 7 - 3 - 1 - 2 } ; int k = 4 ; Console . WriteLine ( SumOfKsubArray ( arr k )); } } // This code is contributed by gauravrajput1
JavaScript // JavaScript program to find sum of all minimum and maximum // elements Of Sub-array Size k. // Returns sum of min and max element of all subarrays // of size k function SumOfKsubArray ( arr k ) { let sum = 0 ; // Initialize result // The queue will store indexes of useful elements // in every window // In deque 'G' we maintain decreasing order of // values from front to rear // In deque 'S' we maintain increasing order of // values from front to rear let S = []; let G = []; // Process first window of size K let i = 0 ; for ( i = 0 ; i < k ; i ++ ) { // Remove all previous greater elements // that are useless. while ( S . length != 0 && arr [ S [ S . length - 1 ]] >= arr [ i ]) S . pop (); // Remove from rear // Remove all previous smaller that are elements // are useless. while ( G . length != 0 && arr [ G [ G . length - 1 ]] <= arr [ i ]) G . pop (); // Remove from rear // Add current element at rear of both deque G . push ( i ); S . push ( i ); } // Process rest of the Array elements for ( ; i < arr . length ; i ++ ) { // Element at the front of the deque 'G' & 'S' // is the largest and smallest // element of previous window respectively sum += arr [ S [ 0 ]] + arr [ G [ 0 ]]; // Remove all elements which are out of this // window while ( S . length != 0 && S [ 0 ] <= i - k ) S . shift ( 0 ); while ( G . length != 0 && G [ 0 ] <= i - k ) G . shift ( 0 ); // remove all previous greater element that are // useless while ( S . length != 0 && arr [ S [ S . length - 1 ]] >= arr [ i ]) S . pop (); // Remove from rear // remove all previous smaller that are elements // are useless while ( G . length != 0 && arr [ G [ G . length - 1 ]] <= arr [ i ]) G . pop (); // Remove from rear // Add current element at rear of both deque G . push ( i ); S . push ( i ); } // Sum of minimum and maximum element of last window sum += arr [ S [ 0 ]] + arr [ G [ 0 ]]; return sum ; } // Driver code let arr = [ 2 5 - 1 7 - 3 - 1 - 2 ]; let k = 4 ; console . log ( SumOfKsubArray ( arr k )); // This code is contributed by _saurabh_jaiswal
Výstup
18
Časová složitost: O(n)
Pomocný prostor: O(k)
