请问如下递推伪代码的T(i)表达式具体代表什么含义？

表达式解读验证 #

你的解读完全准确。我们可以把这个递推式的逻辑拆分对应如下：

• 整个式子是典型的动态规划状态递推式，最常见于最长递增子序列（LIS）相关的问题场景，T(i)代表数组a第i位对应的状态值（通常是到i位为止的符合要求的最长子序列长度）
• 冒号后的1 < j < i-1限定了遍历的索引范围：仅考虑索引大于1、小于i-1的所有j
• a[j] < a[i]是过滤条件：只保留数组j位元素值小于i位元素值的情况
• 对所有符合上述两个条件的T(j)取最大值，再加1，代表把当前a[i]加入子序列后，状态值在之前最长符合要求的子序列基础上累加1

额外补充：如果不存在满足条件的j，空集合的最大值通常约定为0，此时T(i) = 1，对应仅包含a[i]自身的子序列长度。

内容的提问来源于stack exchange，提问作者jreyez