Error when trying to display processed data

IamBC

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:

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.
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.
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)
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));

}
@

ChrisW67

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?

IamBC

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!

Qt World Summit: Submit your Presentation

Error when trying to display processed data