设定n个整数序列为数组arr[0,1,..,n−1]。为了构造问题的最优解，再定义一个整型数组id[0,1,..,n−1]，其中第i项（id[i]）表示数组arr[i,i+1,..,n−1]形成的序列的最长非降子序列中，大于或等于arr[i]的下一个整数（arr[id[i]]）在数组arr中的下标。根据上述最优解转移等式，首先计算的是数组子序列arr[n−2,n−1]的最优解，再然后计算数组子序列