#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();
}