.
Im Normalfall kann man von der Eingabegröße einer Aufgabe auf die erwartete Laufzeitkomplexität schließen. Ein Algorithmus mit linearer Laufzeit, also O(N), schafft es ziemlich gut, innerhalb einer Sekunde 1000000 Werte zu verarbeiten.
Angenommen, man betrachtet die Aktienkursänderung an einem bestimmten Tag p und kennt das Maximum m(p-1) aller Summen der Kursänderungen von einem Tag a mit a<p bis zum Tag p-1. Dann ist das Maximum m(p) aller Summen der Kursänderungen von einem Tag a mit a≤p bis zum Tag p entweder m (p-1) + value [p] oder 0, falls dieser Wert kleiner als 0 ist.
Das gesuchte Maximum ist dann das Maximum aller m (p) für 1≤p≤N. Man kann nun natürlich alle m(p) nacheinander erzeugen und jeweils überprüfen, ob ein neuer Maximalwert ermittelt wurde. Sollte das der Fall sein, muss man noch die zugehörige Startposition und Länge speichern. Das ganze benötigt nicht einmal mehr das value Feld, denn es wird ja auf die Werte in der gleichen Reihenfolge zugegriffen, in der sie in der Eingabedatei stehen.
#include <cstdio>
using namespace std;
int N;
int main ()
{
FILE *fin = fopen ("aktie.in", "r"),
*fout = fopen ("aktie.out", "w");
fscanf (fin, "%d", &N);
int maxStart = 1, maxLen = 0, curStart = 1, len = 0;
float maxValue = 0, summe = 0;
for (int pos = 0; pos < N; pos++) {
float value;
fscanf (fin, "%f", &value);
summe += value;
len++;
if (summe > maxValue) { // neues Maximum
maxValue = summe;
maxStart = curStart;
maxLen = len;
}
if (summe < 0) { // alles zurücksetzen
curStart = pos+2;
len = 0;
summe = 0;
}
}
fprintf (fout, "%d\n%d\n", maxStart, maxLen);
fclose (fin); fclose (fout);
return 0;
}
Wie bereits erwähnt, liegt die Laufzeitkomplexität bei O(N), denn die einzige Schleife des Programms wird für jede Kursänderung einmal durchlaufen. Sogar die Speicherkomplexität wurde verbessert, sie ist jetzt unabhängig von N, nämlich konstant, also O(1).