算法——最长上升子序列（DP和二分）

给定一个无序的整数数组，找到其中最长上升子序列的长度。
输入: [10,9,2,5,3,7,101,18]
输出: 4

纯DP

解体思路：利用动态规划的方法，从一个方向遍历数组，每次获取以该位置为子序列结尾的长度。状态表示，利用数组f分别表示以该位结尾的最长上升子序列；状态转移，像前遍历，如果前者比后者小，则取二者最大长度，最后在加一，表示加上当前位。

PS：现在做dp的题自然而然能够想到闫氏DP分析法，首先想到如何用数组表示每个状态，再去思考怎么递推状态。

class Solution {

    public int lengthOfLIS(int[] nums) {

        int n = nums.length;

        // 状态表示

        int[] f = new int[n];

        int res = 0;

        for(int i = 0; i < n; i++) {

            int cur = 0;

            for(int j = i - 1; j >= 0; j--) {

                if(nums[i] > nums[j]) {

                	// 获取前面最长子序列

                    cur = Math.max(f[j], cur);

                }

            }

			// 状态转移

            f[i] = cur + 1;

            res = Math.max(f[i], res);

        }

        return res;

    }

}

DP + 二分

解题思路：遍历数组，利用一个队列，保存遍历时当前的最长子序列。然后通过二分的方法，查找当前元素在队列中的位置，如果当前元素在队列元素的范围之内，则替换第一个大于等于它的元素，如果当前元素大于队列的最大元素，则直接将当前元素放在最后，同时最长子序列的值增加1。

为什么可以替换中间的值？
因为替换的是第一个大于等于它的值，这样既可以保持队列递增，还可以降低队列元素的值。

class Solution {

    public int lengthOfLIS(int[] nums) {

        int[] f = new int[nums.length];

        int res = 0;

        for(int num : nums) {

           int l = 0, r = res;

           while(l < r) {

               int mid = l + r >> 1;

               if(f[mid] >= num) {

                   r = mid;

               } else {

                   l = mid + 1;

               }

           } 

           f[r] = num;

           if(res == r) res ++;

        }

        return res;

    }

}

巴特西

算法——最长上升子序列（DP和二分）

纯DP

DP + 二分

最新文章

热门文章