Created
June 9, 2010 11:28
-
-
Save metaxy/431348 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <QtCore/QCoreApplication> | |
#include <QList> | |
#include <QLinkedList> | |
#include <QtDebug> | |
QList<int> l; | |
int alg4( QList<int> list) | |
{ | |
int max = 0; | |
int mright = 0; | |
foreach(int i, list) { | |
mright = qMax(mright+i,0); | |
max = qMax(max,mright); | |
} | |
return max; | |
} | |
int alg3(int left, int right) | |
{ | |
if(left > right) return 0; | |
if(left == right) return qMax(0,l.at(right)); | |
int middle = (left+right)/2; | |
int lmidmax = 0; | |
int sum = 0; | |
for(int pos = left; pos <= middle;pos++) { | |
sum += l.at(pos); | |
lmidmax = qMax(lmidmax,sum); | |
} | |
int rmidmax = 0; | |
sum = 0; | |
for(int pos = middle + 1; pos <= right; pos++) { | |
sum += l.at(pos); | |
rmidmax = qMax(rmidmax,sum); | |
} | |
int leftmax = alg3(left,middle); | |
int rightmax = alg3(middle+1,right); | |
return qMax(qMax(lmidmax+rmidmax,leftmax),rightmax); | |
} | |
int alg3(QList<int> list) | |
{ | |
l = list; | |
return alg3(0,list.size()-1); | |
} | |
int alg2a(QList<int> list) | |
{ | |
int max = 0; | |
for(int left = 0; left < list.size();left++) { | |
int sum = 0; | |
for(int right = left; right < list.size();right++) { | |
//if(left < right) { | |
sum += list.at(right); | |
if(sum > max) max = sum; | |
// } | |
} | |
} | |
return max; | |
} | |
int alg2b(QList<int> list) | |
{ | |
QVector<int> sums = list.toVector(); | |
for(int i = 1; i < sums.size(); i++) { | |
sums[i] = sums[i-1] + sums[i]; | |
} | |
int max = 0; | |
for(int left = 0; left < list.size(); left++) { | |
for(int right = left; right < list.size(); right++) { | |
int sum = sums[right]; | |
if(left > 0) sum -= sums[left-1]; | |
if(sum > max) max = sum; | |
} | |
} | |
return max; | |
} | |
int alg1(QList<int> list) | |
{ | |
int max = 0; | |
for(int left = 0; left < list.size();left++) { | |
for(int right = left; right < list.size();right++) { | |
int sum = 0; | |
for(int k = left;k < right +1;k++) { | |
sum += list.at(k); | |
} | |
if(sum > max) max = sum; | |
} | |
} | |
return max; | |
} | |
int main(int argc, char *argv[]) | |
{ | |
QCoreApplication app(argc, argv); | |
QList<QList<int> > bList; | |
QList<int> a ; | |
a << 1 << -1 << 10 << 1 << 2 << -10 << 4 << 6 << 7; | |
bList << a; | |
a.clear(); | |
a << 0 << 0 << 1 << -1 << 1 << -2; | |
bList << a; | |
a.clear(); | |
a << 100 << -100 << 1 << 2; | |
bList << a; | |
a.clear(); | |
a << -1<< -2 << -3; | |
bList << a; | |
a.clear(); | |
a << 0 << 0 << 0<< 0 << 0; | |
bList << a; | |
foreach(QList<int> list, bList) { | |
qDebug() << "ret1 = " << alg1(list); | |
qDebug() << "ret2a = " << alg2a(list); | |
qDebug() << "ret2b = " << alg2b(list); | |
qDebug() << "ret3 = " << alg3(list); | |
qDebug() << "ret4 = " << alg4(list); | |
qDebug() << "\n"; | |
} | |
return app.exec(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment