// O(n*k) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // Initialize result  int max_sum = INT_MIN;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

// O(n*k) solution for finding maximum sum of // a subarray of size k #include  #include  #include  // Find maximum between two numbers. int max(int num1, int num2) {  return (num1>num2) ? num1 : num2; } // Returnează suma maximă într-un subbary de mărimea k. int maxSum(int arr[], int n, int k) { // Inițializare rezultat int max_sum = INT_MIN;  // Luați în considerare toate blocurile care încep cu i.  pentru (int i = 0; i< n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%d', maxSum(arr, n, k));  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

// Java code O(n*k) solution for finding maximum sum of // a subarray of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // Initialize result  int max_sum = Integer.MIN_VALUE;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed by Aditya Kumar (adityakumar129)>

# code import sys # O(n * k) solution for finding # maximum sum of a subarray of size k INT_MIN = -sys.maxsize - 1 # Returns maximum sum in a # subarray of size k. def maxSum(arr, n, k): # Initialize result max_sum = INT_MIN # Consider all blocks # starting with i. for i in range(n - k + 1): current_sum = 0 for j in range(k): current_sum = current_sum + arr[i + j] # Update result if required. max_sum = max(current_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 n = len(arr) print(maxSum(arr, n, k)) # This code is contributed by mits>

// C# code here O(n*k) solution for // finding maximum sum of a subarray // of size k using System; class GFG {  // Returns maximum sum in a  // subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // Initialize result  int max_sum = int.MinValue;  // Consider all blocks starting  // with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.Max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

function maxSum(arr, n, k) {  let max_sum = 0;    // Loop from i to k  for (let i = 0; i < k; i++) {  max_sum += arr[i];  }    let window_sum = max_sum;  for (let i = k; i < n; i++) {  window_sum = window_sum - arr[i - k] + arr[i];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum; } // Driver code let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]; let k = 4; let n = arr.length; console.log(maxSum(arr, n, k));>

 // code ?>// O(n*k) soluție pentru găsirea sumei maxime a // un subgrup de mărimea k // Returnează suma maximă într-un subbary de dimensiune k. function maxSum($arr, $n, $k) { // Initializeaza rezultatul $max_sum = PHP_INT_MIN ; // Luați în considerare toate blocurile // începând cu i. pentru ( $i = 0; $i< $n - $k + 1; $i++) { $current_sum = 0; for ( $j = 0; $j < $k; $j++) $current_sum = $current_sum + $arr[$i + $j]; // Update result if required. $max_sum = max($current_sum, $max_sum ); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67. ?>>>>  
  Ieșire      Complexitatea timpului:    O(k*n) deoarece conține două bucle imbricate.  
    Spațiu auxiliar:    O(1)
 
    Aplicarea tehnicii ferestrei glisante:     
 
Calculăm suma primelor k elemente din n termeni folosind o buclă liniară și stocăm suma în variabilă    window_sum    .
Apoi vom parcurge liniar peste matrice până când ajunge la sfârșit și vom urmări simultan suma maximă.
Pentru a obține suma curentă a unui bloc de k elemente, trebuie doar să scădeți primul element din blocul anterior și să adăugați ultimul element al blocului curent.
Reprezentarea de mai jos va clarifica modul în care fereastra alunecă peste matrice.
  
Luați în considerare o matrice    arr[]    = {5, 2, -1, 0, 3} și valoarea lui    k    = 3 și    n    = 5
 
Aceasta este faza inițială în care am calculat suma inițială a ferestrei pornind de la indicele 0. În această etapă, suma ferestrei este 6. Acum, setăm suma maximă ca fereastra curentă, adică 6.  
 
 
 
 
Acum, glisăm fereastra după un index de unitate. Prin urmare, acum renunță la 5 din fereastră și adaugă 0 la fereastră. Prin urmare, vom obține noua noastră sumă a ferestrei scăzând 5 și apoi adăugând 0. Deci, suma ferestrei noastre devine acum 1. Acum, vom compara această sumă ferestrei cu suma_maximum. Deoarece este mai mic, nu vom modifica suma_maximum.  
 
 
 
 
  
În mod similar, acum încă o dată glisăm fereastra noastră cu un indice de unitate și obținem ca suma nouă fereastră să fie 2. Din nou verificăm dacă această sumă a ferestrei curente este mai mare decât maximum_sum până acum. Încă o dată, este mai mic, astfel încât să nu schimbăm maximum_sum.  
Prin urmare, pentru tabloul de mai sus, suma noastră maximă este 6.
 
 
 
Mai jos este codul pentru abordarea de mai sus:
C++ 
// O(n) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // n must be greater  if (n <= k) {  cout << 'Invalid';  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = max(max_sum, window_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; }>
 Java 
// Java code for // O(n) solution for finding // maximum sum of a subarray // of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // n must be greater  if (n <= k) {  System.out.println('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed // by prerna saini.>
 Python3 
# O(n) solution for finding # maximum sum of a subarray of size k def maxSum(arr, k): # length of the array n = len(arr) # n must be greater than k if n <= k: print('Invalid') return -1 # Compute sum of first window of size k window_sum = sum(arr[:k]) # first sum available max_sum = window_sum # Compute the sums of remaining windows by # removing first element of previous # window and adding last element of # the current window. for i in range(n - k): window_sum = window_sum - arr[i] + arr[i + k] max_sum = max(window_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 print(maxSum(arr, k)) # This code is contributed by Kyle McClay>
 C# 
// C# code for O(n) solution for finding // maximum sum of a subarray of size k using System; class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // n must be greater  if (n <= k) {  Console.WriteLine('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.Max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>
 JavaScript 
>>>PHP>>>  
  Ieșire      Complexitatea timpului:    O(n), unde    n    este dimensiunea matricei de intrare    arr[]    .  
    Spațiu auxiliar:    O(1)
matematică aleatoare java
 
 2. Cel mai mic subbary cu o sumă mai mare decât o valoare dată: 
Dată o matrice    arr[]    de numere întregi și un număr    X    , sarcina este de a găsi cel mai mic subbary cu o sumă mai mare decât valoarea dată.
 
    Abordare:     
  
Putem rezolva această problemă utilizând Tehnica ferestrei glisante și menținând două indicatoare: start și sfârșit pentru a marca începutul și sfârșitul ferestrei. Putem continua să creștem indicatorul de final până când suma ferestrei este mai mică sau egală cu X. Când suma ferestrei devine mai mare decât X, înregistrăm lungimea ferestrei și începem să mutăm indicatorul de început până la suma ferestrei. devine mai mică sau egală cu X. Acum, când suma devine mai mică sau egală cu X, începeți din nou să creșteți indicatorul final. Continuați să mutați indicatorul de început și de final până ajungem la sfârșitul matricei.
 
 3. Găsiți subbarra cu suma dată într-o matrice de numere întregi nenegative: 
Dată o matrice    arr[]    de numere întregi nenegative și un număr întreg    sumă    , găsiți un subbary care se adaugă la un dat    sumă    .
 
    Abordare:    
  
Ideea este simplă, deoarece știm că toate elementele din subgrup sunt pozitive, deci, dacă un subbary are o sumă mai mare decât    suma dată    atunci nu există nicio posibilitate ca adăugarea de elemente la subbarra curentă să fie egală cu suma dată. Deci, ideea este să folosiți o abordare similară cu a    fereastra glisanta    .
 
Începeți cu un subbaraj gol.
se adaugă elemente la subbary până când suma este mai mică decât      X         (suma dată)    .
Dacă suma este mai mare decât      X      , eliminați elementele din    start    a subbarajului actual.
 4. Cea mai mică fereastră care conține toate caracterele șirului în sine: 
    Abordare:    
  
Practic, o fereastră de caractere este menținută prin utilizarea a doi pointeri și anume    start    și    Sfârşit    . Aceste    start    și    Sfârşit    pointerii pot fi folosiți pentru a micșora și, respectiv, a mări dimensiunea ferestrei. Ori de câte ori fereastra conține toate caracterele șirului dat, fereastra este micșorată din partea stângă pentru a elimina caracterele suplimentare și apoi lungimea sa este comparată cu cea mai mică fereastră găsită până acum.  
Dacă în fereastra actuală, nu mai pot fi șterse caractere, atunci începem să creștem dimensiunea ferestrei folosind    Sfârşit    până când toate caracterele distincte prezente în șir sunt și ele acolo în fereastră. În cele din urmă, găsiți dimensiunea minimă a fiecărei ferestre.
 
Exersați probleme la tehnica ferestrei glisante:
Problemă
 
Problemă Link
 
 Găsiți Subarray cu suma dată 
 
 Rezolva 
 
 Maximum fereastră glisantă (Maximul tuturor sub-serilor de dimensiune K) 
 
 Rezolva 
 
 Cel mai lung sub-matrice cu suma K 
 
 Rezolva 
 
 Găsiți suma maximă (sau minimă) a unui subgrup de mărimea k 
 
 Rezolva 
 
 Cea mai mică fereastră dintr-un șir care conține toate caracterele altui șir 
 
 Rezolva 
 
 Lungimea celui mai lung subșir fără caractere repetate 
 
 Rezolva 
 
 Primul număr întreg negativ din fiecare fereastră de dimensiunea k 
 
 Rezolva 
 
 Numărați elemente distincte în fiecare fereastră de dimensiune k 
 
 Rezolva 
 
 Cea mai mică fereastră care conține toate caracterele șirului în sine 
 
 Rezolva 
convertește matricea de octeți în șir
 
 Cea mai mare sumă subgrupă cu cel puțin k numere 
 
 Rezolva 
 
Articole similare:
 R Articole recente despre tehnica ferestrelor glisante 
 Practicați întrebări despre fereastra glisantă 
 DSA Self-Paced – Cel mai folosit și de încredere curs despre DSA