CODEWITHSUNDEEP
c++
user715165
user715165

Reputation:

C++ reading a sequence of integers

gooday programers. I have to design a C++ program that reads a sequence of positive integer values that ends with zero and find the length of the longest increasing subsequence in the given sequence. For example, for the following sequence of integer numbers:

1 2 3 4 5 2 3 4 1 2 5 6 8 9 1 2 3 0

the program should return 6 i have written my code which seems correct but for some reason is always returning zero, could someone please help me with this problem.

Here is my code: 

#include <iostream> 
using namespace std; 

int main() 
{ 
    int x = 1;          // note x is initialised as one so it can enter the while loop
    int y = 0; 
    int n = 0;

    while (x != 0)          // users can enter a zero at end of input to say they have entered all their numbers
    { 
        cout << "Enter sequence of numbers(0 to end): ";
        cin >> x; 
        if (x == (y + 1))   // <<<<< i think for some reason this if statement if never happening 
        { 
            n = n + 1;
            y = x;
        } 
        else 
        {
            n = 0;
        }
    } 
    cout << "longest sequence is: " << n << endl;
    return 0; 
}

Upvotes: 1

Views: 11131

Answers (7)

David Rodr&#237;guez - dribeas
David Rodr&#237;guez - dribeas

Reputation: 208343

I think that there are more than one problem, the first and most important that you might have not understood the problem correctly. By the common definition of longest increasing subsequence, the result to that input would not be 6 but rather 8.

The problem is much more complex than the simple loop you are trying to implement and it is usually tackled with Dynamic Programming techniques.

On your particular code, you are trying to count in the if the length of the sequence for which each element is exactly the successor of the last read element. But if the next element is not in the sequence you reset the length to 0 (else { n = 0; }), which is what is giving your result. You should be keeping a max value that never gets reset back to 0, something like adding in the if block: max = std::max( max, n ); (or in pure C: max = (n > max? n : max );. Then the result will be that max value.

Upvotes: 0

Dennis
Dennis

Reputation: 3731

this is wrong logically:

if (x == (y + 1))   // <<<<< i think for some reason this if statement if never happening 
    {

Should be 

if(x >= (y+1))
{

Upvotes: 0

Nim
Nim

Reputation: 33655

In your program, you have made some assumptions, you need to validate them first.

  1. That the subsequence always starts at 1
  2. That the subsequence always increments by 1

If those are correct assumptions, then here are some tweaks

  1. Move the cout outside of the loop
  2. The canonical way in C++ of testing whether an input operation from a stream has worked, is simply test the stream in operation, i.e. if (cin >> x) {...}
  3. Given the above, you can re-write your while loop to read in x and test that x != 0
  4. If both above conditions hold, enter the loop
  5. Now given the above assumptions, your first check is correct, however in the event the check fails, remember that the new subsequence starts at the current input number (value x), so there is no sense is setting n to 0.
  6. Either way, y must always be current value of x.

If you make the above logic changes to your code, it should work.

Upvotes: 1

Morvader
Morvader

Reputation: 2313

You always return 0, because the last number that you read and process is 0 and, of course, never make x == (y + 1) comes true, so the last statement that its always executed before exiting the loop its n=0

Hope helps!

Upvotes: 0

Kien Truong
Kien Truong

Reputation: 11381

In the last loop, your n=0 is execute before x != 0 is check, so it'll always return n = 0. This should work.

if(x == 0) {
    break;
} else if (x > y ) {
   ...
} else {
   ...
}

Upvotes: 1

Ed.
Ed.

Reputation: 176

If you just want a list of increasing numbers, then your "if" condition is only testing that x is equal to one more than y. Change the condition to:

if (x > y) {

and you should have more luck.

Upvotes: 0

House
House

Reputation: 3496

You also need to reset your y variable when you come to the end of a sequence.

Upvotes: 0

Related Questions