You are given an integer array of size . You are also given queries. In each query, you are given three integers , , and respectively. You are required to determine the length of the largest contiguous segment in the indices range of that forms an arithmetic progression with a common difference of . Note: the segment whose length is always forms an arithmetic progression of a common difference .
Answers
Answer:
simple solution is to one by one consider every pair as first two elements of AP and check for the remaining elements in sorted set. To consider all pairs as first two elements, we need to run a O(n^2) nested loop. Inside the nested loops, we need a third loop which linearly looks for the more elements in Arithmetic Progression (AP). This process takes O(n3) time.
We can solve this problem in O(n2) time using Dynamic Programming. To get idea of the DP solution, let us first discuss solution of following simpler problem.
Given a sorted set, find if there exist three elements in Arithmetic Progression or not
Please note that, the answer is true if there are 3 or more elements in AP, otherwise false.
To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). We start from the second element and fix every element as middle element. For an element set[j] to be middle of AP, there must exist elements ‘set[i]’ and ‘set[k]’ such that set[i] + set[k] = 2*set[j] where 0 <= i < j and j < k <=n-1.
How to efficiently find i and k for a given j? We can find i and k in linear time using following simple algorithm.
Initialize i as j-1 and k as j+1