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.

Spoiler za Kod:

#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).