CKTIS / C
Klizni prozor za nenegativne vrijednosti
Klizni prozor održava neprekinuti odsječak polja i pomiče njegove granice bez ponovnog zbrajanja svih elemenata pri svakom pomaku. Varijanta koja sužava prozor zahtijeva nenegativne ulazne vrijednosti.
Verzija: C23; repository compiler flag, production runtime not attested
Sintaksa
Use this shrinking-window rule only when all input values are nonnegative and the target is strictly positive. Use a running-sum type that can represent every intermediate sum without overflow, including the sum immediately after adding an element and before shrinking the window. Maintain left and right window boundaries and add each entering value to the running sum. While the current sum is at least the target, compare the current window length with the shortest found so far and update it if needed. Then subtract the leftmost value and advance the left boundary, even if that removal drops the sum below the target. An empty window has sum zero, so the positive target ensures that the loop stops before attempting to remove another element.Klizni prozor određen je lijevom i desnom granicom. Pomicanjem desne granice sljedeća se vrijednost dodaje trenutačnom zbroju. Kad zbroj dosegne prag, lijeva se granica pomiče udesno sve dok je uvjet ispunjen, a uklonjene se vrijednosti oduzimaju. Svaki element ulazi u prozor najviše jednom i izlazi iz njega najviše jednom. Prolazak kroz polje zato traje linearno vrijeme.
Nužno je da ulazne vrijednosti budu nenegativne. Dodavanje nenegativnog broja ne može smanjiti zbroj, a njegovo uklanjanje slijeva ne može ga povećati. Ta monotonost omogućuje sigurno sužavanje prozora. Za negativne vrijednosti to zaključivanje više ne vrijedi i potreban je drugi algoritam.
Primjer traži najkraći neprekinuti odsječak čiji je zbroj barem 7. Za 2, 1, 5, 2, 3, 2 program ispisuje 2 jer odsječak 5, 2 ispunjava uvjet.
Primjeri
#include <stddef.h>
#include <stdio.h>
int main(void) {
const int values[] = {2, 1, 5, 2, 3, 2};
const size_t count = sizeof values / sizeof values[0];
const int target = 7;
size_t left = 0;
size_t best = count + 1;
int sum = 0;
for (size_t right = 0; right < count; ++right) {
sum += values[right];
while (sum >= target) {
const size_t length = right - left + 1;
if (length < best) best = length;
sum -= values[left++];
}
}
if (best == count + 1) printf("none\n");
else printf("%zu\n", best);
return 0;
}Rezultat
2
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.