[程序员代码面试指南]最长递增子序列(二分,DP)

题目

例：arr=[2,1,5,3,6,4,8,9,7] ，最长递增子序列为1，3，4，8，9

题解

step1:找最长连续子序列长度

dp[]存以arr[i]结尾的情况下，arr[0..i]中的最长递增子序列的长度。
额外加一个ends[]数组，初始化ends[0]=arr[0],其他为0。有一个有效区ends[0,r],只有有效区内的数才有意义。ends[i]=num表示遍历到目前，所有长度i+1的递增序列中，结尾最小的数时num。
遍历arr[i]时，在ends有效区找最左边>=arr[i]的数，从左到右找的过程表示能连在arr[i]前的连续序列的长度在不断增加。
- 若找到,记为ends[j],说明ends[j]及其后面的数都大于arr[I],故则dp[i]=j+1,ends[j]更新
- 若没找到，说明ends[]有效区的数都比arr[i]小，故dp[i]=有效区长度+1,有效区右边界r++，ends[r]更新。
因为ens[]是一个非递减序列，所以可以使用二分查找
时间复杂度O(nlogn)

step2:输出最长连续子序列元素

找到dp[]中存储的值=最长长度的元素，记为dp[i]对应的arr[i]即为最后一个元素。再往前找存储的值=最长长度-1&&对应的arr[j]<arr[i]的位置，即为倒数第二元素...

其他

这道题用到很经典的一种二分查找：找第一个比给定值大的元素的二分查找。
最终一定是l=r=mid，那么当最后一个元素大于所给元素,l指向它，l即所得。反之，++l，l也即所得。
所以：循环条件带=号，返回的是l，如果未找到将返回右边界+1的位置。

代码

public class Main {

	public static void main(String args[]) {

		int[] arr= {2,1,5,3,6,4,8,9,7};

		int[] incSec=getLongestIncSeq(arr);

		for(int num:incSec) {

			System.out.println(num);

		}

	}

	public static int[] getLongestIncSeq(int[] arr) {

		if(arr==null||arr.length==0) {

			return null;

		}

		int[] dp=getDp(arr);

		return getIncSeq(dp,arr);

	}

        //得到dp数组

	public static int[] getDp(int[] arr) {

		int[] dp=new int[arr.length];

		dp[0]=1;

		int[] ends=new int[arr.length];

		ends[0]=arr[0];

		int end=0;

		for(int i=0;i<arr.length;++i) {//遍历arr

			int pos=firstBigger(arr[i],ends,end);//遍历ends

			if(pos!=end+1) {//找到比arr[i]大的上升子序列结尾元素

				//更新dp和ends

				dp[i]=pos+1;//长度+1

				ends[pos]=Math.min(ends[pos], arr[i]);

			}

			else {//未找到比arr[i]大的上升子序列结尾元素

				//更新dp和ends

				dp[i]=end+1+1;//原长度+1

				++end;

				ends[end]=arr[i];

			}

		}

		return dp;

	}

        //二分查找第一个比num小的元素

	public static int firstBigger(int num,int[] ends,int end) {//二分查找第一个比num小的元素

		int l=0;

		int r=end;

		while(l<=r) {//**

			int mid=(l+r)/2;//

			if(ends[mid]>=num) {

				r=mid-1;//

			}

			else {

				l=mid+1;//

			}

		}

		return l;//**

	}

        //输出最长递增子序列

	public static int[] getIncSeq(int[] dp,int[] arr) {

		int len=Integer.MIN_VALUE;//代表新数组长度 ，并表示新数组索引

		int pos=-1;

		for(int i=0;i<dp.length;++i) {

			len=len>dp[i]?len:dp[i];

			pos=len>dp[i]?pos:i;//dp索引，arr索引

		}

		int[] incSeq=new int[len];

		incSeq[--len]=arr[pos];

		for(int j=pos;j>=0;--j) {

			if(dp[j]==len&&arr[j]<arr[pos]) {

				incSeq[--len]=arr[j];

				pos=j;

			}

		}

		return incSeq;

	}

}

巴特西

[程序员代码面试指南]最长递增子序列(二分,DP)

题目

题解

其他

代码

最新文章

热门文章