// 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>numero2) ? numero1 : numero2; } // Palauttaa maksimisumman alitaulukossa, jonka koko on k. int maxSum(int arr[], int n, int k) { // Alusta tulos int max_sum = INT_MIN;  // Tarkastellaan kaikkia i:llä alkavia lohkoja.  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]);  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) ratkaisu k-koon //-koon alitaulukon maksimisumman löytämiseen // Palauttaa maksimisumman k-koon alitaulukossa. funktio maxSum($arr, $n, $k) { // Alusta tulos $max_sum = PHP_INT_MIN ; // Tarkastellaan kaikkia lohkoja // alkaen kirjaimella i. for ( $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. ?>>>  
  Lähtö      Aika monimutkaisuus:    O(k*n), koska se sisältää kaksi sisäkkäistä silmukkaa.  
    Aputila:    O(1)
 
    Liukuikkunatekniikan soveltaminen:     
 
Laskemme ensimmäisen k elementin summan n termistä lineaarisen silmukan avulla ja tallennamme summan muuttujaan    window_sum    .
Sitten kuljemme lineaarisesti taulukon yli, kunnes se saavuttaa lopun, ja samalla seuraamme maksimisummaa.
Saadaksesi k-elementin lohkon nykyisen summan, vähennä ensimmäinen elementti edellisestä lohkosta ja lisää nykyisen lohkon viimeinen elementti.
Alla oleva esitys tekee selväksi, kuinka ikkuna liukuu taulukon yli.
  
Harkitse taulukkoa    arr[]    = {5, 2, -1, 0, 3} ja arvo    k    = 3 ja    n    = 5
 
Tämä on alkuvaihe, jossa olemme laskeneet alkuikkunan summan indeksistä 0 alkaen. Tässä vaiheessa ikkunan summa on 6. Nyt asetamme maksimisummaksi nykyinen_ikkuna eli 6.  
 
 
 
 
Nyt liu'utamme ikkunaamme yksikköindeksin verran. Siksi se nyt hylkää 5 ikkunasta ja lisää 0:n ikkunaan. Näin ollen saamme uuden ikkunan summan vähentämällä 5 ja lisäämällä siihen 0. Joten ikkunasummamme tulee nyt 1. Nyt verrataan tätä ikkunasummaa maksimi_summaan. Koska se on pienempi, emme muuta enimmäissummaa.  
 
 
 
 
  
Vastaavasti liu'utamme nyt jälleen ikkunaamme yksikköindeksin verran ja saamme uuden ikkunan summaksi 2. Tarkistamme jälleen, onko tämä nykyinen ikkunan summa suurempi kuin tähän asti maksimi_summa. Jälleen kerran se on pienempi, joten emme muuta enimmäissummaa.  
Siksi yllä olevan taulukon maksimi_summa on 6.
 
 
 
Alla on koodi yllä olevalle lähestymistavalle:
paras hentai
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.>
 Python 3 
# 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>>  
  Lähtö      Aika monimutkaisuus:    O(n), missä    n    on syöttötaulukon koko    arr[]    .  
    Aputila:    O(1)
 
 2. Pienin alitaulukko, jonka summa on suurempi kuin annettu arvo: 
Annettu joukko    arr[]    kokonaislukuja ja lukuja    X    , tehtävänä on löytää pienin alitaulukko, jonka summa on suurempi kuin annettu arvo.
 
    Lähestyä:     
  
Voimme ratkaista tämän ongelman käyttämällä Sliding Window Technique -tekniikkaa ja ylläpitämällä kahta osoitinta: alku ja loppu merkitsemään ikkunan alkamista ja loppua. Voimme kasvattaa loppuosoitinta, kunnes ikkunan summa on pienempi tai yhtä suuri kuin X. Kun ikkunan summasta tulee suurempi kuin X, kirjataan ikkunan pituus ja aloitetaan siirtämällä aloitusosoitinta ikkunan summaan asti. muuttuu pienemmäksi tai yhtä suureksi kuin X. Nyt kun summasta tulee pienempi tai yhtä suuri kuin X, aloita taas lopetusosoittimen kasvattaminen. Jatka aloitus- ja loppuosoittimen siirtämistä, kunnes olemme saavuttaneet taulukon loppuun.
 
 3. Etsi alitaulukko annetulla summalla ei-negatiivisten kokonaislukujen joukosta: 
Annettu joukko    arr[]    ei-negatiivisista kokonaisluvuista ja kokonaisluvusta    summa    , etsi alitaulukko, joka lisää annettuun    summa    .
 
    Lähestyä:    
  
Idea on yksinkertainen, koska tiedämme, että kaikki alitaulukon elementit ovat positiivisia, joten jos alitaulukon summa on suurempi kuin    annettu summa    silloin ei ole mahdollista, että elementtien lisääminen nykyiseen alitaulukkoon on yhtä suuri kuin annettu summa. Ideana on siis käyttää samanlaista lähestymistapaa kuin a    Liukuikkuna    .
 
Aloita tyhjästä alaryhmästä.
lisää elementtejä alitaulukkoon, kunnes summa on pienempi kuin      x         ( annettu summa )    .
Jos summa on suurempi kuin      x      , poista elementit    alkaa    nykyisestä alaryhmästä.
 4. Pienin ikkuna, joka sisältää kaikki itse merkkijonon merkit: 
    Lähestyä:    
  
Periaatteessa merkkiikkunaa ylläpidetään käyttämällä kahta osoitinta    alkaa    ja    loppu    . Nämä    alkaa    ja    loppu    osoittimilla voidaan pienentää ja suurentaa ikkunaa vastaavasti. Aina kun ikkuna sisältää kaikki tietyn merkkijonon merkit, ikkunaa pienennetään vasemmalta puolelta ylimääräisten merkkien poistamiseksi ja sitten sen pituutta verrataan pienimpään tähän mennessä löydettyyn ikkunaan.  
Jos nykyisessä ikkunassa ei voi poistaa enempää merkkejä, alamme kasvattaa ikkunan kokoa käyttämällä    loppu    kunnes kaikki merkkijonossa olevat erilliset merkit ovat myös ikkunassa. Etsi lopuksi kunkin ikkunan vähimmäiskoko.
 
Harjoittele ongelmia liukuikkunatekniikassa:
Ongelma
 
Ongelma Linkki
 
 Etsi Subarray annetulla summalla 
 
 Ratkaista 
 
 Liukuva ikkuna maksimi (enintään kaikki K-koon alirivit) 
 
 Ratkaista 
 
 Pisin alitaulukko summalla K 
 
 Ratkaista 
 
 Etsi k-koon alitaulukon maksimi (tai pienin) summa 
 
 Ratkaista 
 
 Merkkijonon pienin ikkuna, joka sisältää kaikki toisen merkkijonon merkit 
 
 Ratkaista 
 
 Pisimmän osamerkkijonon pituus ilman toistuvia merkkejä 
 
 Ratkaista 
 
 Ensimmäinen negatiivinen kokonaisluku jokaisessa k-koon ikkunassa 
 
 Ratkaista 
 
 Laske erilliset elementit jokaisessa k-koon ikkunassa 
 
 Ratkaista 
 
 Pienin ikkuna, joka sisältää kaikki itse merkkijonon merkit 
bool merkkijonoon java
 
 Ratkaista 
 
 Suurin summaalitaulukko, jossa on vähintään k numeroa 
 
 Ratkaista 
 
Aiheeseen liittyvät artikkelit:
 R viimeisimpiä artikkeleita liukuikkunoiden tekniikasta 
 Harjoittele kysymyksiä liukuvasta ikkunasta 
 DSA Self-Paced – DSA:n eniten käytetty ja luotettu kurssi