Musteraufgabe

Ein etwas besserer Ansatz

Wieder wird von jeder Position aus die Länge hochgezählt. Wir müssen allerdings nicht jedesmal alle Werte neu aufaddieren, denn wenn die Länge um 1 erhöht wird, muss zum vorher ermittelten Wert ja nur ein weiterer hinzuaddiert werden.

#include <cstdio>

using namespace std;

float values [1000000];
int N;

int main ()
{
  FILE *fin = fopen ("aktie.in", "r"),
       *fout = fopen ("aktie.out", "w");

  fscanf (fin, "%d", &N);
  for (int n = 0; n < N; n++)
    fscanf (fin, "%f", &values [n]);

  int maxStart = 1, maxLen = 0;
  float maxValue = 0;
  for (int start = 0; start < N; start++) {
    float summe = 0;
    for (int len = 1; start + len <= N; len++) {
      summe += values [start + len - 1];
      if (summe > maxValue) {
        maxValue = summe;
        maxStart = start;
        maxLen = len;
      }
    }
  }

  fprintf (fout, "%d\n%d\n", maxStart, maxLen);

  fclose (fin); fclose (fout);
  return 0;
}

Laufzeit- und Speicherkomplexität

Analysiert man dieses Programm nach derselben Methode wie zuvor, stellt man leicht fest, dass die Laufzeitkomplexität durch O(N^2) und die Speicherkomplexität nach wie vor durch O(N) begrenzt ist. Auch dieser Ansatz ist noch zu langsam, da er nur mit etwa 5000 Werten schnell genug ist.