# Counting the longest increasing subsequence in an array of integers

This is my finished function to find the length of the longest consecutive subsequence of an input array of integers. It's for an assessment so things like the numerical method used and the format of input are out of my hands (int LIS(int* seq, int* temp_seq, int seq_size)). For the temp_seq parameter, the caller will pass an empty array of size seq_size.

As far as I can tell works perfectly, however, our lecturer has barely commented on how to write code that doesn't just do the job but is 'good code' (aka a large amount of the marking criteria).

Is there anything that you can see which could be improved here?

In the past I've lost marks for code that did the job, but didn't follow 'good practice' standards. I've tried to make this code as nice as I can, with a clear logical structure, good commenting etc but I always thought my code was good then because when I tested it it worked. I'm just looking for advice on the form of the code.

int LIS(int* seq, int* temp_seq, int seq_size)
{
/*sets up variables and initial values*/
int i, proceed_flag;
int j = 0, count = -1;

/*this'll be used to ensure each input element is only used once - 1 means not used*/
int use_flag [seq_size];
for (i = 0; i<seq_size; i++)
{
use_flag[i] = 1;
}

/*while the temp array isn't full*/
while(j<seq_size)
{
i = 0;
proceed_flag = 0;

/*drops the next unused number into the temp array*/
while(proceed_flag == 0)
{
if (use_flag[i] == 1)
{
temp_seq[j+1] = seq[i];
use_flag[i] = 0;
//              printf("temp_seq = %d\n", temp_seq[j+1]);
j++;

proceed_flag = 1;
}

i++;
}

/*then drops all smaller numbers from the input array into the temp array*/
for(i = 0; i<seq_size; i++)
{
if(temp_seq[j] > seq[i] && use_flag[i])
{
temp_seq[j+1] = seq[i];
use_flag[i] = 0;
//              printf("temp_seq = %d\n", temp_seq[j+1]);
j++;
}
}

/*this counts the number of repeats - the initialisation value of -1 is just to calibrate the system
it takes an extra loop around and gives a wrong result otherwise*/
count++;
}

return(count);
}

• Can you clarify what the function is supposed to compute? What I understood is "the length of the longest increasing subsequence of consecutive array elements". But for the input array { 1, 2, 1, 3, 1, 4, 1, 5, 1, 6 } the output is 5, and not 2 as I would expect. Commented Nov 2, 2014 at 17:04
• @martinR for the sequence you entered the output should be 6 (if it isn't that's an issue I need to address). you're allowed to ignore any value to make the sequence longer, it's just seeing how many members of the input are in some kind of order. the assignment included a random number generator which feeds the code a sequence like { 4 6 2 5 1 3 } (which in the right order would be 1 2 3 4 5 6) so that test sequence isn't something that the function would expect to receive Commented Nov 2, 2014 at 17:24
• @carrias: So the input is always a permutation of the elements 1, ..., n? Your problem statement is unclear (at least to me) and I would suggest that you update it (perhaps add some instructive sample data). I have compiled your code and the result for { 1, 2, 1, 3, 1, 4, 1, 5, 1, 6 } is 5, and the result for { 4, 6, 2, 5, 1, 3 } is 1. Commented Nov 2, 2014 at 17:29
• @MartinR - I'll have a think about how I can do that. I didn't want to post the whole program as I can't change a lot of it, but it seems that the function isn't working for you the same way that it is for me. would it help to just post the whole code? Commented Nov 2, 2014 at 17:35
• This is what I did: int seq[6] = { 4, 6, 2, 5, 1, 3 }; int temp_seq[6] = { 0 }; int result = LIS(seq, temp_seq, 6); printf("%d\n", result); and the output was 1. So either your function does not work correctly or I am completely misunderstanding what it should do. Commented Nov 2, 2014 at 17:42

/* 1 means not used */
int used_flag[seq_size];


I allowed myself to change the "use" to "used", because it is more grammatically correct.

Now first of all, if "1 means not used", then you should name this array not_used_flag.

Alternatively, you can keep calling it used_flag, but let 0 denote the case of "not used".

If you choose the second option, then you can initialize the entire array upon declaration:

int used_flag[seq_size] = {0};


Please note that it doesn't yield better performance because it's a non-static local array.

Nevertheless, it does clean up your code a bit...

Another point is implied in a comment at the bottom of your code:

/* the initialization value of -1 is just to calibrate the system.
it takes an extra loop around and gives a wrong result otherwise. */


It sounds like an ugly workaround for "an extra loop" that should not take place.

So I think that you definitely need to solve it properly instead of working around it.

Last issue (though possibly related to the previous one):

while (j < seq_size)
{
...
temp_seq[j+1] = ...;
}


By entering the loop with j == seq_size-1, you'll be writing beyond the boundaries of temp_seq.

Your code might be working correctly for some input, but beware that it does look suspiciously unsafe.

• I've implemented those three solutions successfully. the first is a grammatical point, and exactly the kind of thing I was looking for advice about (I find variable names rather arbitrary and can usually learn what something is for pretty quickly even if I name it out of whatever leftovers are on my desk right now). the second I fixed by initialising the count to zero, it simply never should have been -1. the third I fixed by moving the j++; statements to the front of the statement so that I didn't have to access the j+1 th element of anything. my code would always have worked, but looked bad. Commented Nov 5, 2014 at 15:34

There are three significant algorithmic comments i have for this solution to the problem. The first is that, if the method gives you a a temporary storage area, that's a strong hint that you should not need to allocate more space.... int use_flag [seq_size]; is a problem...

The second issue I have, is that this problem can be solved relatively easily (but slowly) with recursion, and no additional space passed in as an argument at all. Recursion has limits on the size of the available stack, but, at the same time, it will be able to accomplish a lot. What the recursive solution does not do, though, is easily short-circuit solutions that are not possible, you can only solve so much without moving state around. Here, by the way, is a recursive solution (not the best answer):

int lis_recurse(int* seq, int seq_size, int* min) {
if (seq_size <= 0)
{
return 0;
}
int without = lis_recurse(seq + 1, seq_size - 1, min);
if (!min || *seq >= *min)
{
int with = 1 + lis_recurse(seq + 1, seq_size - 1, seq);
if (with > without)
{
return with;
}
}
return without;
}

int MyLIS(int* seq, int* temp_seq, int seq_size)
{
return lis_recurse(seq, seq_size, 0);
}


What the recursion shows is that you repeatedly have to solve the 'tail' of the process each time you solve something near the head. That's a lot of repeated work, what if you could 'remember' what you have already calculated?

Where does that lead to? It means that the temporary int array should be used to keep state, and used to optimize the process.

Here's a hint.... If you start at the end of the data, and work backwards, you can count how 'long' the sequence will be from that point, to the end, if that point was included in the result. "Remembering" things like this is a concept called 'memoization'. Since this problem suits memoization so well, it seems natural to include it.

To implement it, you have two loops, the outer one counts from the last element to the first. In that element, you scan the next elements looking for the value that is larger than the current element, that has the longest 'chain' to the end. The loops are simply:

for (int i = seq_size - 1; i >= 0; i--)
{
... // do something here to track the best solution from this point on
for (int j = i + 1; j < seq_size; j++)
{
... // check each solution after this point, looking for the best.
}
temp[i] = ...; // the best possible solution after this point, plus us.
}


Then, at the end, your temp array is populated with the longest solution from any index onwards, and, since we are only interested in the best solution overall, we just need to look for the highest result in the temp array.

So, using memoization, and processing the data from the end of the set to the beginning, you can end up with a relatively efficient $O(n^2)$ algorithm.

Update: the full working implementation would be:

int MemLIS(int* seq, int* temp, int seq_size)
{

for (int i = seq_size - 1; i >= 0; i--)
{
int max = 0;
for (int j = i + 1; j < seq_size; j++)
{
if (seq[j] > seq[i] && temp[j] > max)
{
max = temp[j];
}
}
temp[i] = max + 1;
}

int max = 0;
for (int i = 0; i < seq_size; i++)
{
if (temp[i] > max)
{
max = temp[i];
}
}
return max;
}

• Recursion means additional space on the stack. You could say the stack is allocated to a fixed size when the executable is built, hence, as long as the recursion doesn't cause a stack-overflow, no additional memory is used. But we could just as well claim that OP has allocated the array on the stack, so it's essentially the same memory space that's being used. In any case, as I said at the beginning - recursion consumes memory, there is no magic here. Commented Nov 3, 2014 at 7:07
• @barakmanos - Your comment feels overly pedantic. My answer clearly indicates that space is used on the stack, and the intention was to indicate recursion does not need space passed in as an argument. I have edited the one sentence you chose to criticize so the intention is more clear. Though, given the previous paragraph, and following sentence, it should have been clear already. Finally, the whole point was to use recursion as an anti-suggestion, to say 'don't do it'. Pointing out a problem with a solution I say is not the best feels petty. Commented Nov 3, 2014 at 11:13
• I merely wrote it as a comment on the opening statement of your answer. I later noticed that you implicitly related to that in the second paragraph (suggesting that recursion does consume memory). All that description has changed, so my previous comment is no longer relevant, but in any case, I didn't mean to make it sound like negative criticism (sorry if it did), just to point out that "recursion with no additional space used" was a slightly misleading statement. Commented Nov 3, 2014 at 12:36
• I didn't find this very helpful as I've made it clear this is for an assignment which dictates the numerical method to use and you appear to have used a different method. I didn't really want the code rewritten from scratch in any case, it was two characters away from providing a correct solution in any case. thanks for taking the time though. Commented Nov 5, 2014 at 15:43