Cost function of a dynamic solution to the "longest increasing subsequence" problem

Question

So I have a pretty simple dynamic programming solution to the "longest increasing subsequence" problem (find the longest subsequence of increasing elements in a given sequence, for instance for [1, 7, 2, 6, 4] it would be [1, 2, 4]), which can also find the actual subsequence (as opposed to just lenght):

sequence = [1, 8, 6, 4, 9, 8, 3, 5, 2, 7, 1, 9, 5, 7]
listofincreasing = [[] for _ in range(len(sequence))]
listofincreasing[0].append(sequence[0])

for right in range(1, len(sequence)):
    for left in range(right):
        if (sequence[left] < sequence[right]) and (len(listofincreasing[right]) < len(listofincreasing[left])):
            listofincreasing[right] = [] + listofincreasing[left]
    listofincreasing[right].append(sequence[right])

print(max(listofincreasing, key=len))

These sort of brainteasers are pretty manageable for me, but I don't really know the hard theory behind this. My question is this: How would I go about creating a cost function that would formally describe "how I am filling the list', so to speak? Could someone show me how to approach these problems on this example? Thanks in advance.

Edit - some people asked for a clarification. In the most succint way possible, I would need to create a mathematic function in the the exact same way as it is created here: https://medium.com/@pp7954296/change-making-problem-dynamic-method-4954a446a511 in the "formula to solve coin change using dynamic method:" section, but not for the change making problem but for my solution of the longest increasing subsequence problem

Answer 1

You are looking for a recursive formulation of the overlapping subproblems in your dynamic programming solution.

Let LONGEST(S,x) be the longest increasing subsequence of the first x characters of the sequence S. The solution to the problem is then LONGEST(S,|S|).

Recursively (using 1-based indexing):

LONGEST(S,x) = S[1] if x = 1. Otherwise,
LONGEST(S,x) = the longest of:
    S[x],
    LONGEST(S,y), where 1 <= y < x, or
    LONGEST(S,y) + S[x], where 1 <= y < x and LAST_ELMENT(LONGEST(S,y)) < S[x]

Since LONGEST(S,x) depends only on the values for smaller prefixes, we can produce the values iteratively in order of increasing x, and that is what your program does.