Introduction

The longest convex subsequence problem asks for the largest subsequence whose shape bends upward rather than downward. It is a classic dynamic programming problem because whether a new value can be appended depends on the two values that came before it, not just on the latest value alone.

What Makes a Subsequence Convex

For three consecutive values x, y, and z in a subsequence, the convex condition is:

x + z >= 2 * y

That inequality says the middle value is not larger than the average of its neighbors. Another way to read it is that adjacent differences do not decrease.

Take the array 1, 4, 3, 6, 9.

• The subsequence 1, 3, 6, 9 is convex.
• The check for 1, 3, 6 is 1 + 6 >= 2 * 3, which is true.
• The check for 3, 6, 9 is 3 + 9 >= 2 * 6, which is also true.

Remember that a subsequence does not need to be contiguous. You may skip values, but you must keep the original order.

Why a One-Dimensional DP Is Not Enough

A common first attempt is to store dp[i], the best convex subsequence ending at index i. That loses information. To decide whether a[k] can be appended, you must know the last two chosen values, not only the last one.

The correct state is usually:

dp[i][j] = length of the longest convex subsequence ending with a[i], a[j]

If you want to extend that subsequence with a[k], where i < j < k, you check:

a[i] + a[k] >= 2 * a[j]

If the condition holds, then:

dp[j][k] = max(dp[j][k], dp[i][j] + 1)

Every pair can start a subsequence of length 2, so the base case is simple.

Dynamic Programming Implementation

The following Python function returns both the length and one valid subsequence:

1def longest_convex_subsequence(nums):
2    n = len(nums)
3    if n == 0:
4        return 0, []
5    if n == 1:
6        return 1, [nums[0]]
7
8    dp = [[2] * n for _ in range(n)]
9    parent = [[None] * n for _ in range(n)]
10
11    best_len = 1
12    best_pair = (0, 0)
13
14    for j in range(n):
15        for k in range(j + 1, n):
16            for i in range(j):
17                if nums[i] + nums[k] >= 2 * nums[j]:
18                    candidate = dp[i][j] + 1
19                    if candidate > dp[j][k]:
20                        dp[j][k] = candidate
21                        parent[j][k] = i
22
23            if dp[j][k] > best_len:
24                best_len = dp[j][k]
25                best_pair = (j, k)
26
27    if best_len == 1:
28        return 1, [nums[0]]
29    if best_len == 2:
30        j, k = best_pair
31        return 2, [nums[j], nums[k]]
32
33    seq = []
34    j, k = best_pair
35    seq.append(nums[k])
36    seq.append(nums[j])
37
38    while parent[j][k] is not None:
39        i = parent[j][k]
40        seq.append(nums[i])
41        j, k = i, j
42
43    seq.reverse()
44    return best_len, seq
45
46
47data = [1, 4, 3, 6, 5, 9, 10]
48length, subsequence = longest_convex_subsequence(data)
49print(length)
50print(subsequence)

Example output:

6
[1, 3, 6, 5, 9, 10]

That output is valid because every consecutive triple satisfies the convex inequality.

Complexity and Practical Use

This straightforward solution uses three nested loops, so the time complexity is O(n^3). The table uses O(n^2) space.

That is acceptable for interview-style inputs or medium-sized arrays, but it is not ideal for very large datasets. If you only need the length and the input has extra structure, there may be optimizations, but the pair-based state remains the key idea.

The implementation above also stores parent pointers so the actual subsequence can be reconstructed. If you only care about the length, you can remove that array and simplify the code a little.

That tradeoff is common in dynamic programming: reconstruction costs a little more memory, but it is often what makes the result actually useful.

Worked Example

Suppose the array is 2, 5, 4, 7.

Start with all pair lengths set to 2:

• 'dp[0][1] = 2'
• 'dp[0][2] = 2'
• 'dp[1][2] = 2'

Now consider whether 7 can extend earlier pairs:

• From 2, 5 to 7: 2 + 7 >= 2 * 5 is false.
• From 2, 4 to 7: 2 + 7 >= 2 * 4 is true, so 2, 4, 7 is convex.
• From 5, 4 to 7: 5 + 7 >= 2 * 4 is also true, so 5, 4, 7 is convex.

This is why the algorithm examines triples while storing results by pairs.

Common Pitfalls

The biggest mistake is using a one-dimensional DP. Convexity depends on the last two selected values, so dp[i] alone cannot represent the full state.

Another common bug is forgetting that every pair is already a valid convex subsequence of length 2. If you initialize with 0 or 1, your transitions produce wrong answers.

Some problems define strict convexity instead of non-strict convexity. In that version, x + z > 2 * y is required. Check the exact statement before coding.

It is also easy to confuse subsequences with subarrays. A subarray is contiguous. A subsequence only preserves order.

Summary

• A convex subsequence satisfies x + z >= 2 * y for every consecutive triple.
• The natural DP state is pair-based: dp[i][j].
• Each valid transition extends a previous pair by one element.
• The straightforward solution runs in O(n^3) time and O(n^2) space.
• Parent pointers let you reconstruct the subsequence, not just its length.