Maximalni zbir N elemenata u nizu

[clzola]

C++
Dat je niz T od N elemenata. Naci maximalan zbir uzastopnih K elemenata.

Input:
U prvom redu se nalaze 2 cijela broja N i K.
U drugom redu se nalazi N cijelih brojeva koje treba ucitati u niz T

Output
U jednom i jedinom redu ispisati maximalan zbir uzastopnih K elemenata.

Ogranicenja:
1 <= N <= 1 000 000, 0 < T[i] <= 1 000
vrijeme: 2 sekunde
memorija: 256MB

Primer:
6 3
10 50 30 20 5 1
-----------------
100

50 + 30 + 20 = 100.




#include <cstdio>

FILE *in;

int maxk(int N, int K, int T[])
{
int prvi;
int zbir = 0;
int max = 0;

int i;
for(i=0; i<K-1; i++)
zbir += T[i];

prvi = 0;

for(i; i<N; i++) {
zbir += T[i];
if(zbir > max) max = zbir;

zbir = zbir - T[prvi];
prvi++;
}

return max;
}

int main()
{
in = fopen("test.txt", "r");
int N;
int K;
int *T;

fscanf(in, "%d %d", &N, &K);

T = new int [N];
for(int i=0; i<N; i++)
fscanf(in, "%d", &T[i]);

printf("%d", maxk(N, K, T));

fclose(in);
return 0;
}




Moj algoritam je slozenosti O(N). Prvo sabere prvih K-1 element i zapamti poziciju prvog elementa. Zatim doda sledeci element, uporedi sa trenutnom max vrijednoscu, a onda od zbira oduzme prvi element, i opet dodaje sledeci element, uporedjuje sa max i sve tako u krug dok ne stigne do kraja...

Postoji li neki algoritam koji radi mnogo brze ... na primer za O(log n);

[Geomaster]

Jok. Logaritamsko vreme može da ti se pojavi u problemima u kojima se veličina problema geometrijski smanjuje (recimo, binary search, gde se veličina problema smanjuje dva puta sa svakim upoređivanjem). U ovom slučaju cenim da ne bi postojao efikasniji algoritam, mada možda može nešto dinamičkim programiranjem da se izvuče. Sad žurim, probaću kad se vratim.

EDIT: Mjok, ne uspevam da dobijem manje od O(n).

#include <cstdio>
typedef unsigned int uint32;

int main(void)
{
uint32 sum = 0, n = 0, k = 0, maxSum = 0;
scanf("%u %u", &n, &k);

uint32 *nums = new uint32[n];
for (uint32 i = 0; i < n; ++i)
{
scanf("%u", nums + i);
if (i > k-1)
{
sum += nums[i];
sum -= nums[i-k];
}
else sum += nums[i];

if (sum > maxSum) maxSum = sum;
}
printf("%u", maxSum);
return 0;
}
Moguće da ne radi, iz glave sam pisao...
EDIT 2: U je, nisam video da si ti već dao svoj kôd.

[pyost]

Može se jednostavno videti da efikasnije nikako ne može od O(n), jer u svakom slučaju moraš proći barem jednom kroz svaki element niza, a to je onda već O(n).