定义dp[i]表示以第i个元素结尾的最长递增子序列长度，初始值dp[i] = 1，状态转移方程为dp[i] = max(dp[i], dp[j] + 1)，其中0 ≤ j < i 且 arr[j] < arr[i]，该解法时间复杂度为O(n²)

可以通过贪心+二分查找的方法将LIS问题的时间复杂度优化到O(nlogn)，该优化方法属于线性动态规划的优化实现范畴

线性动态规划的核心特点是状态转移仅依赖于前面已经计算完成的前置状态，求解顺序按照序列的线性顺序从前到后递推

如果将问题改为求最长非递减子序列，只需要将O(n²)解法中状态转移的判断条件arr[j] < arr[i]修改为arr[j] <= arr[i]，同时dp数组的初始值需要修改为0