000
20.11.2005, 16:09 Uhr
~mimi_parapluie
Gast
|
gegeben ist ein feld v der länge n über die ganzen zahlen z.
gesucht ist ein intervall [i; j], welches von allen möglichen intervallen in v die größte zahlensumme enthält.
z.b: das feld v= {-4, 6, 3, -2, 8, 2, -5, 3} enthält 17 als lokale maximale zahlensumme im intervall [1; 5].
nun mein lösungsansatz, der jedoch vollkommen falsche werte liefert. leider hab ich mich schon so verrannt, dass mir schon komplett der plan fehlt.
wäre über jede hilfe dankbar, auch ein ganz neuer ansatz (wie etwa eine saubere brute-force-attacke) wär okay.
danke!
| C++: |
#include <iostream>
#include <cmath>
using std::abs;
using std::cout;
using std::endl;
int main() {
int n = 8;
int a[] = {-4, 6, 3, -2, 8, 2, -5, 3};
int max = 0;
bool erste = true;
int lastmax = 0;
int i, j;
int lasti, lastj;
for (int k = 0; k <= n - 1; k++) {
if (a[k] > 0) {
max = max + a[k];
j = k;
if (erste) {
i = k;
erste = false;
}
} else {
if (abs(a[k]) < max && abs(a[k]) < abs(a[k+1])) {
max = max + a[k];
j = k;
if (max > lastmax) {
lastmax = max;
//max = 0;
erste = true;
lasti = i;
lastj = j;
}
}
}
}
cout << "[" << lasti << "; " << lastj << "]" << endl;
cout << lastmax << endl;
/*cout << i << endl;
cout << j << endl;
cout << max << endl;*/
return 0;
}
|
|
