CODEWITHSUNDEEP
carraysalgorithm
Fëanor Tang
Fëanor Tang

Reputation: 151

Algorithm for determining max increasing sequence in an array

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

Upvotes: 0

Views: 280

Answers (1)

John Bollinger
John Bollinger

Reputation: 180306

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.

Upvotes: 1

Related Questions