Call us

Data Structures and Algorthims

An arithmetic sequence is a sequence of numbers where the difference between successive terms, the sequence’s stride, is constant. For example, [8, 19, 30, 41] is an arithmetic sequence with stride 11 because 19–8 = 30–19 = 41–30 = 11.
Suppose that, given a list, you need to find a maximum arithmetic sequence that indexes strictly increasing terms. For instance, from the list [70,20,60,30,40,10,0,60], the values 20, 40, and 60 are three values in increasing order that are evenly spaced in the list (appearing at indices 1, 4, and 7), but there is no way to select four such terms. That means that [1, 4, 7] is a longest suitable arithmetic sequence of indices. This problem can be solved by exhaustive search.
Write python method find_longest_suitable_sequence so that it takes in a list of numbers and returns a maximum arithmetic sequence that indexes strictly increasing terms from that list. For example, for find_longest_suitable_sequence([70, 20, 60, 30, 40, 10, 0, 60]), [1, 4, 7] is a solution.
A na ̈ıve exhaustive search that considers every possible indexing by an arithmetic sequence will run slowly on most large inputs. Try to find a way to reduce the search space so that the algorithm uses far fewer array accesses on typical inputs. You will receive 5 bonus points if you incorporate these measures to improve the performance.

Both comments and pings are currently closed.

Comments are closed.

Powered by WordPress | Designed by: Premium WordPress Themes | Thanks to Themes Gallery, Bromoney and Wordpress Themes