Longest Increasing Subsequence

The following code shows how OptFlow solves the Longest Increasing Subsequence problem (Leetcode) with dynamic programming

# Author: Anonymized for paper review
# Case Study: longest increasing subsequence

import optflow as flow
import numpy as np

np.random.seed(0)

N = 9
a = flow.Constant(value=np.array([-10, 10, 9, 2, 5, 3, 7, 11, 8]))
x = flow.Variable(cat=flow.binary, shape=(N, ))
p = flow.Constant(value=0, dtype=flow.int64)  # record the largest value in the subsequence
obj = flow.Constant(value=0.)

constraints = []
with flow.ForLoop(N) as i:
    with flow.IfCond(x[i]):     # if the i-th element is selected into the subsequence
        constraints.append((a[i] > a[p]) | (p == 0))    # keep the sequence increasing
        p = i                   # update p
        obj += 1                # update total length of the sequence

prob = flow.Problem(objective=obj, constraints=constraints, sense=flow.maximize)
prob.solve(solver=flow.dp)
print(x.optimized_value)
res = [a_i for a_i, x_i in zip(a.value, x.optimized_value) if x_i]
print(a.value)
print(res)

Output:

searching state space...
state size: 37
Time elapsed: 0.09 s
[1 0 0 1 0 1 1 0 1]
[-10  10   9   2   5   3   7  11   8]
[-10, 2, 3, 7, 8]

[Run Online Demo] (password: )