Error when trying to display processed data



  • Hello, I am making a program, which basically takes values which would represent points, and will compute the maximum sub-array of these points. The layout is simple -> a QLabel which will eventually show the result, a QLineEdit where the user will enter his text and a QPushButton which will trigger the slot.

    The Slot will do 3 things:

    1. It will read the user input. Since the LineEdit returns a string, and the numbers are originally seperated by a string, we will think up of a way to deal with that.
      We will store this information in a vector.

    2. In order for us to be able to implement the Max_Subarray algorithm, we need to compute the data. We Will use a new vector, where we will store the data. The new vector will have 1 less element than the old one and the way we will compute it is the following. We will start from 1 until the end of the vector and we will substract the i-1'th element from the ith element.

    3. Now that we can process the data we will run a version of the maximum subarray algorithm (there are several, I have implemented an iterative linear time one)

    4. Set the value of the label of the sum.

    All should be well, but I have a mistake somewhere. I am getting wierd output. Sometimes 0, sometimes very long numbers... I am aplying the function.
    One final thing:
    QVector<int> vec;
    QVector<int> comp;
    These guys are declared in the header file.
    Oh also, here is an example user input: 10, 5, 6, 3

    @void MainWindow :: compute()
    {
    // Read user input
    QString numbers = ui->lineEdit->text();
    QString tmp; // create temp string which will be used to store the temp substrings of each int
    numbers+=" ";
    for(int i = 0; i < numbers.length()-1; i++)
    {
    if(numbers[i].isDigit())
    {
    tmp +=numbers[i];
    }
    else
    {
    bool ok = true;
    int iTime = tmp.toInt(&ok, 10);
    vec.push_back((iTime));
    tmp="";
    }
    }
    //compute the real vector that we will search the max subarray from
    for(int i = 1; i < vec.size(); i++)
    {
    comp.push_back(vec[i] - vec[i-1]);
    }

    //compute the max subarray
    
       int  max_sum = -9999;
       int sum = 0;
       for(int i = 0; i < comp.size(); i++)
       {
           sum += comp[i];
           if(sum > max_sum)
               max_sum = sum;
           if(sum < 0)
               sum = 0;
       }
      // print the answer (sum);
       ui->label->setText(QString::number(sum));
    

    }
    @



  • Nothing to do with Qt.

    You are expecting your example input to get sum = 1 but you will be getting sum = 0
    because you have incorrectly implemented "Kadane's algorithm":http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm It's important to return the maximum sum, not the last sum.
    @
    int kadanes(const QVector<int> &comp)
    {
    int max_ending_here(0);
    int max_so_far(0);
    foreach(int x, comp) {
    max_ending_here = qMax(0, max_ending_here + x);
    max_so_far = qMax(max_so_far, max_ending_here);
    }
    return max_so_far;
    }
    @

    BTW: Are you emptying comp and vec between runs? Is there a reason these vectors are not local variables?



  • I found the reason for the bug- > there was one extra zero at the end of the vector after the reading of the input is over. Just pop_back the vector and the code will work.

    And then there is the mistake which you pointed out.

    The problem is solved, thank you for the help!


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.