Qt Forum

    • Login
    • Search
    • Categories
    • Recent
    • Tags
    • Popular
    • Users
    • Groups
    • Search
    • Unsolved

    Error when trying to display processed data

    General and Desktop
    2
    3
    1255
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • I
      IamBC last edited by

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

      }
      @

      1 Reply Last reply Reply Quote 0
      • C
        ChrisW67 last edited by

        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?

        1 Reply Last reply Reply Quote 0
        • I
          IamBC last edited by

          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!

          1 Reply Last reply Reply Quote 0
          • First post
            Last post