SPOJ - Black or White (BORW)

Problem Statement:
SPOJ - BORW

Summary:
Given a sequence of number a[i], we can paint a number either white or black, or we can leave it unpainted. The white numbers must form a strictly decreasing subsequence, while the black numbers must be a strictly increasing subsequence. Find the minimum number of unpainted numbers.

Solution:
Lately I've been presented with problems that appears to be an LDS/LIS problem, but after working on them for quite a while then I realize that I've been fooled again (cry). Anyway, this problem can be solved recursively in a very simple manner: let S(dec, inc, idx) be the maximum number of painted numbers from idx to N, where the last element in the decreasing subsequence has index dec, and last element of the increasing subsequence has index inc. Then:
S(dec, inc, idx) = maximum of:
1. If a[dec] > a[idx], consider 1 + S(idx, inc, idx+1)
2. If a[inc] < a[idx], consider 1 + S(dec, inc, idx+1)
3. Either way, consider S(dec, inc, idx+1)

But the running time is pretty bad on SPOJ judge (like, nearly 40s wow), I think there are better implementations/ideas that can push it down to a few seconds top. The bottom up version of this approach will run faster for sure.