Tuesday 28 July 2015

Longest positive sequence in array

Find longest positive sequence in given array

Suppose arr = {-5, -1, 1, 2, 3, -9, 9, 8, 7, 6, 5, -3, -9, -8}

For this array, longest positive sequence is 5, starting at index 6.   

import java.util.Objects;

public class PositiveSeq {
 public static String getLongestPositiveSequence(int arr[]) {
  Objects.nonNull(arr);

  int maxSequence = -1;
  int count = 0;
  int i = 0, endIndex = -1;

  for (i = 0; i < arr.length; i++) {
   if (arr[i] > 0) {
    count++;
   } else {
    if (count > maxSequence) {
     maxSequence = count;
     endIndex = i - 1;
    }
    count = 0;
   }
  }

  if (count > maxSequence) {
   maxSequence = count;
   endIndex = i - 1;
  }

  if (endIndex == -1) {
   return "No positive Sequence";
  }

  return "sequence starts from " + (endIndex - maxSequence + 1)
    + " end at " + endIndex;

 }
}


Following is the junit test case for above program.
import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class PositiveSeqTest {

 @Test
 public void test1() {
  int arr1[] = { 1, 2, -3, 2, 3, 4, -6, 1, 2, 3, 4, 5, -8, 5, 6 };
  int arr2[] = { 1, -3, 2, 1, 5, 4, 7, 8, 4, 6, 7, 3, 9, 1 };
  int arr3[] = { -1, -2, -3, -2, -3, -4, -6, -1, -2, -3, -4, -5, -8, -5,
    -6 };
  int arr4[] = { -1, -2, -3, -2, -3, -4, -6, -1, -2, -3, -4, -5, -8, -5,
    6 };
  int arr5[] = { 1, 2, 3, 2, 3, -4, -6, 1, 2, 3, 4, 5, -8, 5, 6 };
  int arr6[] = { 1, 2, 3, 2, 3, 4, 6, 1, 2, 3, 4, 5, 8, 5, 6 };
  int arr7[] = { 1 };
  int arr8[] = { -1 };
  int arr9[] = {};

  String expected1 = "sequence starts from 7 end at 11";
  String expected2 = "sequence starts from 2 end at 13";
  String expected3 = "No positive Sequence";
  String expected4 = "sequence starts from 14 end at 14";
  String expected5 = "sequence starts from 0 end at 4";
  String expected6 = "sequence starts from 0 end at 14";
  String expected7 = "sequence starts from 0 end at 0";
  String expected8 = "No positive Sequence";

  assertEquals(expected1, PositiveSeq.getLongestPositiveSequence(arr1));
  assertEquals(expected2, PositiveSeq.getLongestPositiveSequence(arr2));
  assertEquals(expected3, PositiveSeq.getLongestPositiveSequence(arr3));
  assertEquals(expected4, PositiveSeq.getLongestPositiveSequence(arr4));
  assertEquals(expected5, PositiveSeq.getLongestPositiveSequence(arr5));
  assertEquals(expected6, PositiveSeq.getLongestPositiveSequence(arr6));
  assertEquals(expected7, PositiveSeq.getLongestPositiveSequence(arr7));
  assertEquals(expected8, PositiveSeq.getLongestPositiveSequence(arr8));
  assertEquals(expected8, PositiveSeq.getLongestPositiveSequence(arr9));
 }

 @Test(expected = NullPointerException.class)
 public void test2() {
  PositiveSeq.getLongestPositiveSequence(null);
 }
}


No comments:

Post a Comment