// 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; } // Atgriež maksimālo summu k izmēra apakšmasīvā. int maxSum(int arr[], int n, int k) { // Inicializēt rezultātu int max_sum = INT_MIN;  // Apsveriet visus blokus, kas sākas ar 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]);  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) risinājums, lai atrastu // k izmēra apakšmasīva maksimālo summu // Atgriež maksimālo summu k izmēra apakšmasīvā. function maxSum($arr, $n, $k) { // Inicializēt rezultātu $max_sum = PHP_INT_MIN ; // Apsveriet visus blokus // sākot ar 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. ?>>>  
  Izvade      Laika sarežģītība:    O(k*n), jo tajā ir divas ligzdotas cilpas.  
    Palīgtelpa:    O(1)
 
    Bīdāmo logu tehnikas pielietošana:     
 
Mēs aprēķinām pirmo k elementu summu no n vārdiem, izmantojot lineāro cilpu un saglabājam summu mainīgajā    loga_summa    .
Tad mēs lineāri šķērsosim masīvu, līdz tas sasniegs beigas, un vienlaikus sekosim līdzi maksimālajai summai.
Lai iegūtu k elementu bloka pašreizējo summu, vienkārši atņemiet pirmo elementu no iepriekšējā bloka un pievienojiet pašreizējā bloka pēdējo elementu.
Tālāk redzamais attēlojums skaidri parādīs, kā logs slīd pa masīvu.
  
Apsveriet masīvu    arr[]    = {5, 2, -1, 0, 3} un vērtība    k    = 3 un    n    = 5
 
Šī ir sākotnējā fāze, kurā mēs esam aprēķinājuši sākotnējā loga summu, sākot no indeksa 0. Šajā posmā loga summa ir 6. Tagad mēs iestatām maksimālo_summu kā pašreizējo_logu, t.i., 6.  
 
 
 
 
Tagad mēs pabīdām logu pa vienības indeksu. Tāpēc tagad tas izmet 5 no loga un pievieno logam 0. Tādējādi mēs iegūsim savu jauno logu summu, atņemot 5 un pēc tam pievienojot tai 0. Tātad, mūsu loga summa tagad kļūst par 1. Tagad mēs salīdzināsim šo loga summu ar maksimālo_summu. Tā kā tas ir mazāks, mēs nemainīsim maksimālo_summu.  
 
 
 
 
  
Līdzīgi, tagad atkal mēs pabīdām mūsu logu ar vienības indeksu un iegūstam jaunā loga summu 2. Atkal mēs pārbaudām, vai šī pašreizējā loga summa ir lielāka par maksimālo_summu līdz šim. Atkal tas ir mazāks, tāpēc mēs nemainām maksimālo_summu.  
Tāpēc iepriekšminētajam masīvam mūsu maksimālā_summa ir 6.
 
 
 
Tālāk ir norādīts iepriekš minētās pieejas kods:
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>>  
  Izvade      Laika sarežģītība:    O(n), kur    n    ir ievades masīva lielums    arr[]    .  
    Palīgtelpa:    O(1)
 
 2. Mazākā apakšgrupa, kuras summa ir lielāka par doto vērtību: 
Dots masīvs    arr[]    no veseliem skaitļiem un skaitļa    X    , uzdevums ir atrast mazāko apakšmasu, kuras summa ir lielāka par doto vērtību.
 
    Pieeja:     
  
Mēs varam atrisināt šo problēmu, izmantojot Sliding Window Technique un saglabājot divus rādītājus: sākumu un beigas, lai atzīmētu loga sākumu un beigas. Mēs varam turpināt palielināt beigu rādītāju, līdz loga summa ir mazāka vai vienāda ar X. Kad loga summa kļūst lielāka par X, mēs ierakstām loga garumu un sākam pārvietot sākuma rādītāju līdz loga summai. kļūst mazāka vai vienāda ar X. Tagad, kad summa kļūst mazāka vai vienāda ar X, atkal sāciet palielināt beigu rādītāju. Turpiniet pārvietot sākuma un beigu rādītāju, līdz esam sasnieguši masīva beigas.
 
 3. Nenegatīvu veselu skaitļu masīvā atrodiet apakšgrupu ar norādīto summu: 
Dots masīvs    arr[]    no nenegatīviem veseliem skaitļiem un vesels skaitlis    summa    , atrodiet apakšgrupu, kas papildina doto    summa    .
 
    Pieeja:    
  
Ideja ir vienkārša, jo mēs zinām, ka visi apakšgrupas elementi ir pozitīvi, tāpēc, ja apakšgrupas summa ir lielāka par    dotā summa    tad nepastāv iespēja, ka elementu pievienošana pašreizējam apakšmasīvam būs vienāda ar doto summu. Tāpēc ideja ir izmantot līdzīgu pieeju a    bīdāms logs    .
datortīkli
 
Sāciet ar tukšu apakšgrupu.
pievienojiet elementus apakšgrupai, līdz summa ir mazāka par      x         ( dotā summa )    .
Ja summa ir lielāka par      x      , noņemiet elementus no    sākt    pašreizējā apakšgrupa.
 4. Mazākais logs, kurā ir visas pašas virknes rakstzīmes: 
    Pieeja:    
  
Būtībā rakstzīmju logs tiek uzturēts, izmantojot divus rādītājus    sākt    un    beigas    . Šie    sākt    un    beigas    norādes var izmantot, lai attiecīgi samazinātu un palielinātu loga izmēru. Ikreiz, kad logā ir visas dotās virknes rakstzīmes, logs tiek samazināts no kreisās puses, lai noņemtu papildu rakstzīmes, un pēc tam tā garums tiek salīdzināts ar mazāko līdz šim atrasto logu.  
Ja pašreizējā logā vairs nevar izdzēst rakstzīmes, mēs sākam palielināt loga izmēru, izmantojot    beigas    līdz logā ir redzamas arī visas virknē esošās atšķirīgās rakstzīmes. Visbeidzot, atrodiet katra loga minimālo izmēru.
 
Praktizējiet problēmas ar bīdāmo logu tehniku:
Problēma
 
Problēmas saite
 
 Atrodiet Subarray ar norādīto summu 
 
 Atrisināt 
 
 Bīdāmā loga maksimums (maksimums visu K izmēra apakšbloku skaits) 
upcasting
 
 Atrisināt 
 
 Garākais apakšmasīvs ar summu K 
 
 Atrisināt 
 
 Atrodiet k izmēra apakšmasīva maksimālo (vai minimālo) summu 
 
 Atrisināt 
 
 Mazākais logs virknē, kurā ir visas citas virknes rakstzīmes 
 
 Atrisināt 
 
 Garākās apakšvirknes garums bez rakstzīmēm 
 
 Atrisināt 
 
 Pirmais negatīvs vesels skaitlis katrā k izmēra logā 
 
 Atrisināt 
 
 Saskaitiet atšķirīgus elementus katrā k izmēra logā 
 
 Atrisināt 
 
 Mazākais logs, kurā ir visas pašas virknes rakstzīmes 
 
 Atrisināt 
 
 Lielākā summa apakšgrupa ar vismaz k skaitļiem 
 
 Atrisināt 
 
Saistītie raksti:
 R jaunākie raksti par bīdāmo logu tehniku 
 Praktiski jautājumi par bīdāmo logu 
 DSA Self-Paced — visbiežāk izmantotais un uzticamākais DSA kurss