Suma min i max wszystkich podtablic o rozmiarze k.
Mając tablicę dodatnich i ujemnych liczb całkowitych, zadaniem jest obliczenie sumy minimalnych i maksymalnych elementów wszystkich podtablic o rozmiarze k.
Przykłady:
Wejście : tablica [] = {2 5 -1 7 -3 -1 -2}
K = 4
Wyjście : 18
Wyjaśnienie : Podtablice o rozmiarze 4 to:
{2 5 -1 7} min + maks = -1 + 7 = 6
{5 -1 7 -3} min + maks = -3 + 7 = 4
{-1 7 -3 -1} min + maks = -3 + 7 = 4
{7 -3 -1 -2} min + maks = -3 + 7 = 4
Brakujące tablice podrzędne -
{2 -1 7 -3}
{2 7 -3 -1}
{2 -3 -1 -2}
{5 7 -3 -1}
{5 -3 -1 -2}
i kilka innych – dlaczego nie wzięto ich pod uwagę?
Biorąc pod uwagę brakujące tablice, wynik będzie wynosić 27
Suma wszystkich min i max = 6 + 4 + 4 + 4 = 18
Ten problem jest głównie rozwinięciem poniższego problemu.
Maksimum wszystkich podtablic o rozmiarze k
Naiwne podejście:
C++Wykonaj dwie pętle, aby wygenerować wszystkie podtablice, a następnie wybierz wszystkie podtablice o rozmiarze k i znajdź wartości maksymalne i minimalne. Na koniec zwróć sumę wszystkich elementów maksymalnych i minimalnych.
// 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 ));
Wyjście
18
Złożoność czasowa: NA 2 *k), ponieważ dwie pętle odnajdują całą podtablicę i jedna pętla odnajduje maksymalne i minimalne elementy w podtablicy o rozmiarze k
Przestrzeń pomocnicza: O(1), ponieważ nie wykorzystano dodatkowej przestrzeni
Metoda 2 (przy użyciu zestawu MultiSet):
Pomysł polega na wykorzystaniu struktury danych Multiset i koncepcji przesuwanego okna.
- Po pierwsze tworzymy zestaw wielokrotny pary {numberindex}, ponieważ indeks pomógłby nam w usunięciu i-tego elementu i przejściu do okna o następnym rozmiarze k .
- Po drugie, mamy I I J które są wskaźnikami tyłu i przodu używanymi do utrzymywania okna.
- Przejdź przez tablicę i wstaw do pary wielokrotnej {numberindex}, a także sprawdź rozmiar okna, gdy stanie się on równy k rozpocznij swój główny cel, tj. znalezienie sumy elementów maksymalnych i minimalnych.
- Następnie usuń i-ty numer indeksu ze zbioru i przesuń i-ty wskaźnik do następnej lokalizacji, czyli nowego okna rozmiaru k.
Realizacja:
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 ; }
Wyjście
18
Złożoność czasowa: O(nlogk)
Przestrzeń pomocnicza: O(k)
Metoda 3 (Efektywna metoda usuwania z kolejki):
C++Pomysł polega na wykorzystaniu struktury danych Dequeue i koncepcji przesuwanego okna. Tworzymy dwie puste kolejki dwustronne o rozmiarze k („S” „G”), które przechowują jedynie indeksy elementów bieżącego okna, które nie są bezużyteczne. Element jest bezużyteczny, jeśli nie może być maksimum lub minimum kolejnych podtablic.
// 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
Wyjście
18
Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(k)
