# Longest geometrically increasing subsequence

Given a sorted array of $n$ positive integers, the problem is to find the longest subsequence so that the progression of differences between consecutive elements of the subsequence is geometrically increasing.

Is there any complexity theoretic reason to believe this simple looking problem cannot be solved in $O(n^2)$ time?

added How fast can this problem be solved? Dynamic programming seems to give $O(n^3)$ time.

• Can't we reduce this to longest arithmetically increasing subsequence? Aug 24, 2013 at 7:05
• @Kaveh How? Taking logs does not appear to help. Remember a subsequence looks like start, start+a, start+a r, start +ar^2 etc.
– Simd
Aug 24, 2013 at 7:08
• It seems to me that a similar algorithm to the arithmetic case would work for this one. What is the motivation for this question by the way? I.e. why are you interested in it? Aug 24, 2013 at 7:11
• This note may be helpful. There are essentially no lower bounds known for this kind of problem. Aug 24, 2013 at 20:09
• @Kaveh the problem is that the "obvious" reduction to finding an AP (guess the first element and then take logs) would take $n^3$ time. I think that's what the OP wants to improve on. Aug 25, 2013 at 17:55