DIR Return Create A Forum - Home
       ---------------------------------------------------------
       techsuns
  HTML https://techsuns.createaforum.com
       ---------------------------------------------------------
       *****************************************************
   DIR Return to: Puzzles && Algorithms
       *****************************************************
       #Post#: 443--------------------------------------------------
       arithmetic progression
       By: dinesh Date: February 12, 2013, 10:10 am
       ---------------------------------------------------------
       Given an array of integers A, give an algorithm to find the
       longest Arithmetic progression in it, i.e find a sequence i1 <
       i2 < … < ik, such that
       A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is
       the largest possible.
       The sequence S1, S2, …, Sk is called an arithmetic progression
       if
       Sj+1 – Sj is a constant
       #Post#: 444--------------------------------------------------
       Re: arithmetic progression
       By: kranthipls Date: February 12, 2013, 11:57 pm
       ---------------------------------------------------------
       Is the given array a sequence?
       #Post#: 445--------------------------------------------------
       Re: arithmetic progression
       By: dinesh Date: February 13, 2013, 12:40 am
       ---------------------------------------------------------
       no
       just a random array of numbers
       #Post#: 446--------------------------------------------------
       Re: arithmetic progression
       By: kpr29 Date: February 14, 2013, 10:27 pm
       ---------------------------------------------------------
       Pseudo code:
       Brute Force method: May be correct may be not
       suppose X = x1, x2,....., xn are the numbers
       for each element i in X
       for each j= i + 1 in x
       {
       compute | xi - xj | => y
       put y in  set A if y is not present;
       }
       //set A contains all the contant value
       // next compute set B with two loops and count number of pairs
       have constant values from set A
       //find the max from set B and we will know what is the
       corresponding constant from set A => generate the longest
       seqence.
       @Majeti: I think i made my idea clear....... I have thought of a
       solution with graph... If u validate this, then I will share the
       other one which I thought about.
       kp.
       
       #Post#: 450--------------------------------------------------
       Re: arithmetic progression
       By: dinesh Date: February 15, 2013, 12:32 am
       ---------------------------------------------------------
       @KP: I feel it is correct - what is its complexity?
       *****************************************************