Saturday, June 25, 2016

Max length AltArray

Problem : An array which contains the alternating elements (non-zero) of opposite sign is called as Alt array. Given an array, find the maximum length of sub-array which is AltArray. (Keep it O(N))


E.g. {908,-7654,102354,9,102,-349,25,910987,-11,100,10}
have three sub-array which are AltArray and have a max length of 3, viz. {908,-7654,102354}, {102,-349,25}, {910987,-11,100}.
/*An array which contains the alternating elements (non-zero) of opposite sign is called as Alt array. 
Given an array, find the maximum length of an array which is alternate array. */

public class AltArr{
 static public void main(String...y){
  
  System.out.println(getMaxLength(new long[]{3,-78,9,-18,98,-120,100,1023,-11,12,13})); //7
  System.out.println(getMaxLength(new long[]{1023,-1903,109876,-198})); //4
  System.out.println(getMaxLength(new long[]{10000})); //1
  System.out.println(getMaxLength(new long[]{213,-6100,100987,-2900009,1120,-10,914,-212,101,-815,1})); //11
  System.out.println(getMaxLength(new long[]{908,-7654,102354,9,102,-349,25,910987,-11,100,10})); //3
  System.out.println(getMaxLength(new long[]{1,-1,1,1,1,-1,1,1,-1,1,-1})); //4
 }
 
  static long getMaxLength(long[] a){
  long oldMaxLength = 1, newMaxLength = 1;
  for(int i=1 ; i < a.length ; i++)
  {
   if(a[i]*a[i-1] < 0)
    newMaxLength++;
   else{
    if(newMaxLength > oldMaxLength)
     oldMaxLength = newMaxLength;
    newMaxLength = 1;
   }
  }
  
  return oldMaxLength > newMaxLength ? oldMaxLength : newMaxLength;
 }
}

No comments:

Post a Comment