本文共 1272 字，大约阅读时间需要 4 分钟。

dp概念：在整个数组或在固定大小的滑动窗口中找到总和或最大值或最小值的问题可以通过动态规划（DP）在线性时间内解决

题目： 给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

你算法的时间复杂度应该为 O(n2)

====================================================

思路： 我们知道，在最大连续子列和问题中，dp[i]表示下标为i的元素作为序列末尾时能得到的最大子列和，dp[i]也是问题的状态。 本题也一样，用dp[i]表示下标为i的元素nums[i]作为序列末尾时能得到的最长上升子列的长度，并将dp[i]作为本题的状态。然后将面临两种情况：

nums[i]前面的元素都更大或者与之相等。

nums[i]前面有更小的元素。 第一种情况好办，这说明以nums[i]为序列末尾时能得到的最长上升子列的长度dp[i]为1，因为前面的元素都更大，它们和nums[i]组合，无法形成上升子列。 第二种情况下，我们需要找出前面所有比nums[i]更小的元素nums[j]（其中，j = 0, 1, 2…i-1），并获得它们的dp[j]，而后，dp[i] = max{dp[j] + 1}（j = 0, 1, 2…i-1，且nums[j] < nums[i]）。

至此，状态转移方程就出来了：

dp[i] = max{dp[j] + 1, 1}，其中j = 0,1,2,…,i-1且nums[j] < nums[i]。 边界： dp[0] = 1。以nums[0]为末尾时能得到的最长上升子列的长度肯定为1，因为该子列就只有一个元素nums[0]。 之后，从边界出发，通过状态转移方程，不断计算dp[]数组，dp[]数组中的最大值就是最长上升子列的长度。

class Solution {
       public int lengthOfLIS(int[] nums) {
           if(nums.length == 0){
              return 0;        }        int[] dp = new int[nums.length];        Arrays.fill(dp, 1);        int res = 1;        for(int i=0; i
   
     nums[j]){
                       dp[i] = Math.max(dp[i], dp[j]+1);                }            }            res = Math.max(res, dp[i]);        }        return res;    }}
   

转载地址：http://pswpi.baihongyu.com/