个人网站数据库大小,网站建设设计制作包头,西安seo全网营销,湘潭知名网站建设题目 如题 思路 核心思想是#xff0c;维护一个数组ends#xff0c;它记录了长度为k的子序列的末尾元素的最小值。听起来很抽象#xff0c;我们不妨手动演示一遍整个过程。 假设数组a{2,9,4,27,29,15,7}#xff0c;令length表示当前找到的最长非下降子序列的长度。初始时le…题目 如题 思路 核心思想是维护一个数组ends它记录了长度为k的子序列的末尾元素的最小值。听起来很抽象我们不妨手动演示一遍整个过程。 假设数组a{2,9,4,27,29,15,7}令length表示当前找到的最长非下降子序列的长度。初始时length1ends[1]2。 i1length2ends[2]9 i2length2ends[2]4原因是4比9更容易和后面的数构成非下降子序列 i3length3ends[3]27 i4length4ends[4]29 i5length415能和ends[2]4连接起来并且它比ends[3]27更容易和后面的数构成非下降子序列因此ends[3]15 i6length4end[3]7。 可以看到整个算法就是找到ends中第一个大于当前数的位置。假设当前数为a[i]找到的位置为t说明ends[t-1]a[i]那么a[i]可以和ends[t-1]连接起来构成长度为i的子序列同时ends[t]a[i]说明a[i]要比ends[t]更容易和后面的数构成子序列因此进行替换。可以说算法的思想是贪心加二分。 代码 package com.iqiyi;public class Test {public static void main(String[] args){int[] arraynew int[]{2,9,4,27,29,15,7};int[] endsnew int[array.length1];ends[1]array[0];int length1;for(int i1;iarray.length;i){int low1;int highlength;while(lowhigh){int mid(lowhigh)/2;if(ends[mid]array[i])lowmid1;elsehighmid;}if(ends[low]array[i])ends[low]array[i];else{length;ends[length]array[i];}}System.out.println(length);}
}
复制代码转载于:https://juejin.im/post/5c39b1d26fb9a049a81f8ced
