Suppose given a sequence $X$ of numbers. We want to find the longest subsequence $X′$ of $X$ in which, for each $i$,$$ 2X′[i]<X′[i−1]+X′[i+1].$$
I think this problem is related to the longest increasing subsequence, so I try as follows: Let $X′[i]$ is the length of the longest subsequence that ends in the element at index $X[i]$ ,
$$X′[i+1]=\max\bigg(1,\max_{ j=1..i \\ 2X[i]−X[i−1]<X[i+1]}\bigg(X′[j]+1\bigg)\bigg)$$
Is my idea correct?
