Thursday 24 September 2015

Maximum arithmetic sequence in an array

Problem


You are given an array of integers. Find the length of the longest arithmetic sequence in the array. An arithmetic sequence is contiguous array elements which are in arithmetic progression. 

Solution


We iterate over the array and find the difference between the consecutive elements and keep track of the longest running count of same difference. If current difference is different than the previous difference then we reset the count. If the length of the longest running difference is k. Then the longest arithmetic sequence is of length k+1.


Code

package com.dsalgo;

public class MaxArithmeticSequence {

 public static void main(String[] args) {
  int[]arr={2,5,3,6,9,12,15,34,23};
  findMaxArithmeticSequence(arr);
 }

 private static void findMaxArithmeticSequence(int[] arr) {
  int maxLength=0;
  int currentLength=0;
  int prevDiff=0;
  for(int i=1;i < arr.length;++i)
  {
   if(i==1)
   {
    prevDiff=arr[i]-arr[0];
    currentLength=maxLength=2;
    continue;
   }
   if(prevDiff==arr[i]-arr[i-1])
   {
    currentLength++;
    if(currentLength > maxLength)
     maxLength=currentLength;
   }
   else
   {
    currentLength=2;
    prevDiff=arr[i]-arr[i-1];
   }
  }
  System.out.println("max arithmetic sequence length = "+maxLength);
 }

}

No comments:

Post a Comment