Longest “increasing” subsequence with two consecutive numbers whose average is less than the third number

Question

Problem Statement

Given an array of integers, find the length of the longest subsequence with two consecutive numbers whose average is less than the third number in O(n^3) time.

Example: [20, 10, 5, 0, 6, 4, 15, 6, 9, 8], the longest subsequence that satisfies the requirement is 5, 0, 6, 4, 6, 9, 8, and the length of that sequence is 7. (5 + 0) / 2 = 2.5 < 6, (0 + 6) / 2 = 3.0 < 4, (6 + 4) / 2 = 5.0 < 6, etc.

What I tried

1st approach: O(n^2)

A generic dynamic programming approach, I define the DP array to be the length of the longest subsequence that satisfies the condition.

If (i-2)th and (i-1)th integers’ average is less than ith integer, we add one to the dp array. The solution is the last element of the DP array.

This didn’t work as I realized it is only considering the numbers in the original array, not the subsequence I am trying to achieve. So, this approach only gave me 5 as the answer for the example input above, and the answer would be 5, 0, 6, 4, 15. The approach did not account for disjoint parts of the original sequence to create the new subsequence.

1.5th approach

While writing out the problem on my notes, I realized the corresponding average subsequence for the example input is the longest. Following the idea of a LIS problem, I created an array of all the average numbers to find the longest increasing subsequence in that array. This solved the example input but failed more complicated inputs.

2nd approach: O(n^3)

Using the hint of the problem statement that the algorithm can be O(n^3), so I tried coming up with a definition for a 2D DP array and a loop to make it O(n^3). I defined the DP[i][j] to be the length of the longest subsequence from the start element to the ith element, while considering the jth element.

Considering the example input, for instance, DP[2][6] = 3 because the subsequence would be 10, 5, 15. From the first element to the 2nd index element, we consider the subsequence 10, 5, and the 6th index element is 15, so the subsequence here is 10, 5, 15, and the length is 3. Repeat until every half above the main diagonal of the table is filled, and the solution is the last element (last row, last column) in that half.

I thought this was it, but there were problems I ran into such as not knowing which part of the DP table should i be reusing and not knowing what exactly are my last two numbers of the subsequence I am trying to achieve. Ultimately, I didn’t know where to go next.

Other thoughts

I think a 3D DP array could also work, but I haven’t really thought about how I would define the array…

Any help would be greatly appreciated!