0

I am taking a C language course at Coursera where I came across an assignment asking me to write a piece of code that can tell the maximum increasing sequence in an array. For example, for an array{3,5,0,7,8,9} it should return me three as the max. I wrote two pieces of code which I assume should both be able to pass. However, only one of them did and I couldn't figure out why.

Here is the first piece of code that pass:

#include <stdio.h>
#include <string.h>
size_t maxSeq(int*array, size_t n){
  size_t maxLength = 0;
  size_t counter = 1;
  if(n == 0){
    return maxLength;
  }
  if(n == 1){
    maxLength = 1;
    return maxLength;
  }
  for(int i = 1;i < n;i++){
    if((array[i]-array[i-1])>0){
      counter += 1;
    }else{
      if(maxLength < counter){
        maxLength = counter;
      }
      counter = 1;
    }
  }
  if(maxLength < counter){
    maxLength = counter;
  }
  return maxLength;
}

And here is the second piece of code which didn't pass:

#include <stdio.h>
#include <string.h>
size_t maxSeq(int*array, size_t n){
  int maxLength = 0;
  int counter = 1;
  if( n== 0){
    return maxLength;
  }
  if(n == 1){
    maxLength = 1;
    return maxLength;
  }
  for(size_t i = 1;i < n;i++){
    if((array[i]-array[i-1])>0){
      counter += 1;
      if(counter >= maxLength){
        maxLength = counter;
      }
    }else if((array[i]-array[i-1])<=0){
      counter = 1;
    }
  }
  return maxLength;
}
2
  • 5
    A take it you mean that you want to determine the length of a maximal (strictly) increasing sequence of the array elements. The sequence itself cannot be characterized by a single number. In that case, I don't see why the expected result for {3,5,0,7,8,9} would be 3. The subsequence {0,7,8,9} is strictly increasing and has length 4. Commented Apr 16, 2020 at 16:29
  • Sorry, the length of the maximum increasing sequence should be 4. Commented Apr 17, 2020 at 3:26

1 Answer 1

1

The two codes are substantially equivalent, and the both give me the correct answer (4, not 3) for the example input.

The type differences between n, counter, maxLength, and i produce a bad code smell, and they could in fact cause both codes to fail on inputs whose length is not representable by type int. That is not likely to be the issue that the tester exercised, however, considering that the first code passed.

The main problem with the second code is that it produces an incorrect result (0) for input arrays that are non-increasing, such that the maximal strictly increasing subsequences have length 1. The reason why this is the case is left as an exercise. If you have trouble figuring it out just from reading the code, then consider employing a debugger to follow an execution in detail.

Sign up to request clarification or add additional context in comments.

3 Comments

Thanks for your reply. Do you have any advice on how to avoid problems caused by the type differences? Is it wise that we always keep related variables of the same type?
@FëanorTang, you should be sure everywhere to choose data types that are fit for the purpose to which you put them. That includes being able to represent values at the extremes of the range you need to accommodate. I won't say flatly that one should always match variable types, but usually you should. When you don't, you should be able to explain why that's ok, and as a matter of style, you should strongly consider putting that explanation in a code comment.
Thank you for your clear explanation. It's really helpful.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.