Need help with longest sequence project.

Hello,

I need some help with my assignment, the assignment is to design a program that takes an input list of up to 20 distinct positive integers which is ended by -1. Print out the length and the longest increasing integer sub-sequence of adjacent numbers. I must use one function input the array of values and one to determine the length and sequence of the array.

This is what I have so far and I've pointed out were my error is.
Help would be appreciated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <stdio.h>
#include <iomanip>

void inputArray(int array[], int &n);
int checkArray (int array[], int start);
int determineLengthSequence(int array[], int start, int n);

using namespace std;

int main()
{
	
	int sequence[20], count = 0, start = 1;
;
	inputArray(sequence, count); 
	determineLengthSequence(sequence, start, count);

	return 0;
}

void inputArray (int array[], int &n)
{
    int numbers, i;
    
    cout << "\n" << "Input a list of numbers (No more than 20) :";
    cin >> numbers;
    
    while (numbers != -1) 
    {
       if ( n > 20 )
	   {
			cout << "You have entered a more than 20 numbers." << endl; 

			cout << "\n\n" << "Input a list of numbers (No more than 20) :";
			cin >> numbers;
	   }
	   else
	   {
			array[n] = numbers;
			n++;
			cin >> numbers;
	   }
		 for (i = 0; i < n; i++ )
		{
			cout << setw(5) << array[i];
		}

		cout << endl;
    }
}

int checkArray(int array[], int start) //Checks the array for a sequence
{
	int k;

	for (k = start; array[k] - array[k-1] == 1 && array[k] != -1; k++)
	{
	}

	return k;
}

int determineLengthSequence(int array[], int start, int n)
{
	int end = 0, currentLongest = 0, prevStart, prevEnd, numbers, k;

	while (end <= 20)
	{
		numbers = array[n];
		end = checkArray(numbers, start); // Error C2664: cannot convert parameter 1 from 'int' to 'int []' 
			
		if ( end - start > currentLongest)
		{
			currentLongest = end - start;
			prevStart = start;
			prevEnd = end;
		}
		cout << "Current Longest: " << currentLongest << endl;
		start = end + 1;
	}

	cout << "Lomgest Sequence: \n";
	for(k = prevStart -1; k < prevEnd; k++)
	{
		cout << array[k] << end;
	}

	cout << "Count: " << (prevEnd - prevStart) + 1 << endl;

	return 0;
}
Last edited on
The error is that the variable called 'numbers' is an integer variable not an array so since the function checkArray is expecting an array as it's first parameter, the compiler throws an error because the first parameter is an integer
Thank you for the reply, I set numbers to numbers[20] and that solved the error.

However this is the result I am getting.



Input a list of numbers (No more than 20) :1212789-1
1212789
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Current Longest: 0
Lomgest Sequence:
Press any key to continue . . .
You have to come up with a new method to solve this. The sequence does not have to start at 1.

You just need one for-loop and you are simpy checking if the initial value is smaller than the current one
After removing the checkArray and determineLengthSequence functions, I replaced it with this.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void longestSeqAndLength(int array[], int n) 
{
    int start = 0,currentLongest = 0, prevStart = 0, end = 1, i;
    
	for (i = 1; i < n; i++) 
	{
          if (array[i] > array[i - 1]) 
		  {
             if (i - start + 1 > end) 
	    {
                 end = i - start + 1;
                 prevStart = start;
				 
            }
	   } 
	    else 
		  {
             start = i;
		  }
    }

    cout << "Longest sequence is " << prevStart << endl; 
    cout << "Length of the sequence is " << end << " numbers long." <<      endl;
    for (int i = 0; i < end; i++) 
     {
     }

      cout << endl;
}


This is now my output.


Input a list of numbers (No more than 20) :12789-1

Longest sequence is 0
Length of the sequence is 1 numbers long.

Press any key to continue . . .


I'm out of ideas, guidance would be appreciated, thanks.
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <inttypes.h>
#include <deque>
#include <map>
#define INIT(a,b) memset(a, b, sizeof(a))
#define even(_) ((~_&1))
#define all(G) G.begin(), G.end()
#define MAX 1000000
#define pii pair<int, int>
#define cond(P, E) P = E.begin(); P != E.end(); ++P

using namespace std;

void GetInput( int *p, int &s ){
	for ( int num = 0;  num ^ -1 && s--; *p++ = num )
		cin >> num;
}

string toString ( int num ) {
	stringstream ss;//create a stringstream
	ss << num;//add number to the stream
	return ss.str();//return a string with the contents of the stream
	//http://www.cplusplus.com/forum/beginner/7777/#msg36008
}

int main()
{	
	int count = 1, MaxCount = count, ArraySize = 20, Array[ArraySize];
	GetInput(Array, ArraySize);
	
	string longest = "";
	for ( int t = 1; ( 20 - ArraySize ) > t; ++t ) {
		if ( Array[t] > Array[t-1] ) {
			longest.append( toString( Array[t-1] ) + " " );
			++count;
		}
		else if ( count > MaxCount ) {
			MaxCount = count;
			cout << "Current longest sequence is: " << longest << Array[t-1] << endl;
			longest.clear();
			count = 1;
		}
	}
	cout << "Length of longest sequence is: " << MaxCount << endl;
  	
	return 0;
}
Last edited on
@Smac89:

I was going through your prescribed code and was intrigued by the function below:

1
2
3
void GetInput( int *p, int &s ){
	for ( int num = 0;  num ^ -1 && s--; *p++ = num )
		cin >> num;


I'm still a learner and would like you to explain the loop condition portion
num ^ -1 && s--;
of the for statement. I was also wondering why you're using pointers when you could have more easily input the integers without them.
the '^' symbol is the bitwise exclusive or operator. Here is a link to explain what it does http://www.cprogramming.com/tutorial/bitwise_operators.html
You can easily replace that code with num != -1 and it still means the same thing.

s--, simply decrements s ( simple )

*p++ = num
http://www.cplusplus.com/doc/tutorial/pointers/

When you pass a pointer to an array as a parameter, the pointer is looking at the first spot in the array. So when I do *p++ = num I am assigning that spot the value in num and at the same time I am moving the pointer over 1 spot.
ex:

[*_][_][_][_][_]

*p++ = 5

[5][*_][_][_][_]
@Smac89:

Thanks for your response. I already knew what each character meant in isolation; the one that really threw me off was the ^ character which I mistook for exponentiation. I ran your code several times but the results were not correct. Check out this program output below:


23 1 99 3 96 11 88 19 72 4 69 14 70 39 78 84 85 20 -1
Current longest sequence is: 1 99
Current longest sequence is: 3 11 88
Current longest sequence is: 19 4 14 70
Length of longest sequence is: 4
Press any key to continue . . .


The first line of the longest sequence is correct; the second line is not; and the third line is clearly not!

The correct longest sequence should have been:39 78 84 85.

Here is fixed version if you are still interested:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <inttypes.h>
#include <deque>
#include <map>
#define INIT(a,b) memset(a, b, sizeof(a))
#define even(_) ((~_&1))
#define all(G) G.begin(), G.end()
#define MAX 1000000
#define pii pair<int, int>
#define cond(P, E) P = E.begin(); P != E.end(); ++P

using namespace std;

void GetInput( int *p, int &s ){
	for ( int num = 0;  num ^ -1 && s--; *p++ = num )
		cin >> num;
}

string toString ( int num ) {
	stringstream ss;//create a stringstream
	ss << num;//add number to the stream
	return ss.str();//return a string with the contents of the stream
	//http://www.cplusplus.com/forum/beginner/7777/#msg36008
}

int main()
{	
	int count = 1, MaxCount = count, ArraySize = 20, Array[ArraySize];
	GetInput(Array, ArraySize);
	
	string longest = "";
	for ( int t = 1; ( 20 - ArraySize ) > t; ++t ) {
		if ( Array[t] > Array[t-1] ) {
			longest.append( toString( Array[t-1] ) + " " );
			++count;
			continue;
		}
		else if ( count > MaxCount ) {
			MaxCount = count;
			cout << "Current longest sequence is: " << longest << Array[t-1] << endl;
		}
		longest.clear();
		count = 1;
	}
	cout << "Length of longest sequence is: " << MaxCount << endl;
  	
	return 0;
}
Topic archived. No new replies allowed.