// 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>skaičius2)? skaičius1 : skaičius2; } // Grąžina maksimalią sumą k dydžio pogrupyje. int maxSum(int arr[], int n, int k) { // Inicijuoti rezultatą int max_sum = INT_MIN;  // Apsvarstykite visus blokus, prasidedančius raide i.  už (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) sprendimas ieškant didžiausios // k dydžio pogrupio sumos // Grąžina maksimalią sumą k dydžio pogrupyje. function maxSum($arr, $n, $k) { // Inicijuoti rezultatą $max_sum = PHP_INT_MIN ; // Apsvarstykite visus blokus // pradedant nuo i. už ($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. ?>>>  
  Išvestis      Laiko sudėtingumas:    O(k*n), nes jame yra dvi įdėtos kilpos.  
    Pagalbinė erdvė:    O(1)
 
    Stumdomų langų technikos taikymas:     
 
Mes apskaičiuojame pirmųjų k elementų sumą iš n terminų naudodami tiesinę kilpą ir išsaugome sumą kintamajame    lango_suma    .
Tada mes eisime tiesiškai per masyvą, kol jis pasieks pabaigą, ir tuo pat metu stebėsime maksimalią sumą.
Norėdami gauti dabartinę k elementų bloko sumą, tiesiog atimkite pirmąjį elementą iš ankstesnio bloko ir pridėkite paskutinį dabartinio bloko elementą.
Toliau pateiktame paveikslėlyje bus aišku, kaip langas slysta per masyvą.
  
Apsvarstykite masyvą    arr[]    = {5, 2, -1, 0, 3} ir reikšmė    k    = 3 ir    n    = 5
 
Tai yra pradinis etapas, kai mes apskaičiavome pradinę lango sumą, pradedant nuo indekso 0. Šiame etape lango suma yra 6. Dabar mes nustatome maksimalią_sumą kaip esamą_langą, ty 6.  
 
 
 
 
Dabar slenkame langą vieneto indeksu. Todėl dabar jis išmeta 5 iš lango ir prideda 0 prie lango. Taigi naujojo lango sumą gausime atėmę 5 ir prie jos pridėję 0. Taigi, mūsų lango suma dabar tampa 1. Dabar palyginsime šią lango sumą su maksimalia_suma. Kadangi jis mažesnis, maksimalios_sumos nekeisime.  
 
 
 
 
  
Panašiai, dabar dar kartą slenkame savo langą vieneto indeksu ir gauname naujojo lango sumą, kuri yra 2. Dar kartą patikriname, ar ši dabartinė lango suma yra didesnė už maksimalią_suma iki šiol. Dar kartą jis yra mažesnis, todėl maksimalios_sumos nekeičiame.  
Todėl aukščiau pateiktame masyve mūsų maksimali_suma yra 6.
 
 
 
Žemiau pateikiamas aukščiau pateikto metodo kodas:
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>>  
  Išvestis      Laiko sudėtingumas:    O(n), kur    n    yra įvesties masyvo dydis    arr[]    .  
    Pagalbinė erdvė:    O(1)
 
 2. Mažiausia posistemė, kurios suma didesnė už nurodytą reikšmę: 
Duotas masyvas    arr[]    sveikųjų skaičių ir skaičiaus    X    , užduotis yra rasti mažiausią pogrupį, kurio suma didesnė už nurodytą reikšmę.
gimp šriftai
 
    Metodas:     
  
Šią problemą galime išspręsti naudodami slankiojančio lango techniką ir išlaikydami dvi rodykles: pradžią ir pabaigą, kad pažymėtumėte lango pradžią ir pabaigą. Galime didinti pabaigos žymeklį, kol lango suma yra mažesnė arba lygi X. Kai lango suma tampa didesnė už X, įrašome lango ilgį ir pradedame perkelti pradžios žymeklį iki lango sumos. tampa mažesnė arba lygi X. Dabar, kai suma tampa mažesnė arba lygi X, vėl pradėkite didinti pabaigos rodyklę. Perkelkite pradžios ir pabaigos žymeklį, kol pasieksime masyvo pabaigą.
 
 3. Raskite pogrupį su nurodyta suma neneigiamų sveikųjų skaičių masyve: 
Duotas masyvas    arr[]    neneigiamų sveikųjų skaičių ir sveikasis skaičius    suma    , suraskite pogrupį, kuris papildo duotąjį    suma    .
 
    Metodas:    
  
Idėja paprasta, nes žinome, kad visi pogrupio elementai yra teigiami, taigi, jei pogrupio suma yra didesnė už    duota suma    tada nėra galimybės, kad elementų pridėjimas prie dabartinės pogrupio bus lygus nurodytai sumai. Taigi idėja yra naudoti panašų požiūrį į a    stumdomas langas    .
 
Pradėkite nuo tuščio pogrupio.
pridėti elementus į pogrupį, kol suma bus mažesnė nei      x         ( duota suma )    .
Jei suma didesnė už      x      , pašalinkite elementus iš    pradėti    dabartinio pogrupio.
 4. Mažiausias langas, kuriame yra visi pačios eilutės simboliai: 
    Metodas:    
  
Iš esmės simbolių langas palaikomas naudojant dvi nuorodas    pradėti    ir    galas    . Šie    pradėti    ir    galas    Rodyklės gali būti naudojamos atitinkamai sumažinti ir padidinti lango dydį. Kai lange yra visi nurodytos eilutės simboliai, langas sumažinamas iš kairės, kad būtų pašalinti papildomi simboliai, o tada jo ilgis lyginamas su mažiausiu iki šiol rastu langu.  
Jei dabartiniame lange daugiau simbolių negalima ištrinti, mes pradedame didinti lango dydį naudodami    galas    tol, kol lange taip pat bus visi atskiri eilutėje esantys simboliai. Galiausiai suraskite minimalų kiekvieno lango dydį.
 
Praktikuokite stumdomų langų technikos problemas:
Problema
 
Problemos nuoroda
 
 Raskite Subarray su nurodyta suma 
 
 Išspręsti 
 
 Stumdomo lango maksimumas (daugiausia visų K dydžio posistemių) 
 
 Išspręsti 
 
 Ilgiausias pomasyvas su suma K 
 
 Išspręsti 
 
 Raskite didžiausią (arba mažiausią) k dydžio pogrupio sumą 
 
 Išspręsti 
 
 Mažiausias eilutės langas, kuriame yra visi kitos eilutės simboliai 
 
 Išspręsti 
 
 Ilgiausios eilutės ilgis be pasikartojančių simbolių 
 
 Išspręsti 
 
 Pirmasis neigiamas sveikasis skaičius kiekviename k dydžio lange 
 
 Išspręsti 
 
 Suskaičiuokite skirtingus elementus kiekviename k dydžio lange 
 
 Išspręsti 
 
 Mažiausias langas, kuriame yra visi pačios eilutės simboliai 
 
 Išspręsti 
 
 Didžiausios sumos pogrupis su mažiausiai k skaičiais 
reguliarioji išraiška java
 
 Išspręsti 
 
Susiję straipsniai:
 R Naujausi straipsniai apie stumdomų langų techniką 
 Praktiniai klausimai apie stumdomą langą 
 DSA Self-Paced – dažniausiai naudojamas ir patikimas DSA kursas