首页 > 编程知识 正文

最长严格递增子序列长度,最大连续子序列和问题

时间:2023-05-05 04:31:21 阅读:32917 作者:2989

主题记述给定的数组arr,长度为n,输出arr的最长增加子串。 (如果有多个回答,请输出其中词典顺序最小的)

输入说明:将输出两行,其中包含表示数组长度的正整数n(n=100000 )。 第二行包含表示数组ARR(left(1) leqARR_I ) leq1e9) right )的n个整数(1arri 1e9)。 输出描述:输出一行。 表示你求出的最长的增加子序列。 例1

输入复制

92 1 5 3 6 4 8 9 7输出复印

1 3 4 8 9例2

输入复制

51 2 8 6 4输出复印

1 ) 4表示其最长子串有3个,(1、2、8 )、(1、2、6 )、1、2、4 )其中第3个词典顺序最小,所以答案是) 1、2、4 )最原始的最长子串问题最大

7、1、8、2、9、10、3、1、11字典顺序最小最长的增加部分序列是1、2、9、10、11 .

首先,传统的o(n.^2)复杂度解法,DP ) I )表示以以下符号I结束的最长增加子序列的长度。 那么,整个遍历过程如下。

1. i=7(下标0 ),dp[0]=1

2. i=1(下标1 ),因为此时遍历I之前的所有元素,没有比I小的元素,所以dp[1]=1

3.i=8(下标2 )此时,遍历I之前的所有元素。 首先,j=7,7、7和8可以构成长度为2的增量子串,所以需要更新dp[2]=2,最后打印整个增量子串,所以需要存储8之前的要素为7,所以需要重新排列pre, 制作pre[2]=0,表示下标字符串为2的j=1继续增加,此时由1和8构成的增加部分序列的长度也为2,如果1为8之前的要素,则词典顺序变小,因此pre[2]=1(下标1

4 .遍历4.i=2,所有上述元素,1和2可以构成长度为2的增加子序列2,dp[3]=2,pre[3]=1可以更新。

5. i=9,遍历前面的所有元素,以2结尾的增加子串的长度为2,加上9可以构成长度为3的增加子串,但9前面的其余元素不能构成长度为9和长度为3的增加子串,因此dp[4]=3,pre[4]=3

这样,扫描结束后,dp的最大值对应于下标,是词典顺序最小的最长增加部分序列的最后一个要素。 然后,根据pre序列追溯,可以找到整个系列。

其次是o(nlogn )复杂度的解法,核心思想也是构建pre序列。 与“打印最长子序列长度”的问题一样,利用二分搜索。

构建两个数组len和pre,pre的含义相同,len[i]=j表示长度为I的递增子序列的最后一个元素是j

扫描过程如下

1.i=7,len为空,len[1]=7,pre[7]=0(7() 7前面的元素为下标0 ) ) ) )。

2.i=1,用二分查找查找len中1以上的第一个要素,更新len[1]=1。 (此时,长度为1的递增子串的最后的要素从7变为1,辞典顺序更小) ) 1前面的要素为下标1 ) ) )。

3.i=8大于len的最后一个元素1。 如果将I直接向len推送,则len(2)=8,8之前的要素成为len倒数第2个要素1,因此pre(8)=1) 8之前的要素成为下标1 )。

4. i=2,在len中查找大于或等于2的第一个元素,在8中,更新len[2]=2。 此时,2前面的元素是len倒数第二个元素1,因此pre[2]=1。

5. i=9大于len的最后一个元素。 如果将9直接推送到len,则len [3]=9,9,9前面的要素是len倒数第二个要素2,因此pre[9]=3(9)。 (9前面的要素是下标3 )。

因此,到最后,len的最后一个元素是字典顺序最小的最长递增子序列的最后一个元素,可以根据pre追溯到序列中的所有元素。

ps :在上面的示例中,为了清楚起见,pre数组和len数组包含数组元素的值,并且在实际编程时必须包含数组元素的后缀。 例如,在第一步中,len[1]=7必须更改为len[1]=7 (对应于7的下标)。

代码如下。

# include bits/stdc.husingnamespacestd; int n; 矢量int arr; 语音解决方案(; int main () Scanf ) ' %d ',n ); ARR.resize(n; for(intI=0; in; I ) Scanf('%d”,arr[i]; 求解(; }intbinary_search(intL、int r、int target ); 矢量输入len; //增加子数组长度的void solve () { vectorint pre; pre.resize(n len.reserve(n; len.push_back(0; //len[0]没有实际意义Len.push_back(0; //在初始情况下,len[1]=0表示长度为1的递增序列以arr[0]结束的pre[0]=INT_MIN; //INT_MIN是for(intI=1),指示前面的元素不再存在; in; I ) (/cout ) I=) iendl; if(ARR[I]ARR[Len.size(-1] ) ) Len.push_back ) I; pre[I]=Len[Len.size((-2] ); //cout ' 1: pre [ I ]=' pre [ I ] endl; }else{intindex=binary_search(1,) (int ) len.size )-1,arr[i]; //cout '2' ' :索引='索引; len[index]=i; if(index==1) { pre[i]=INT_MIN; } else { pre [ I ]=len [索引-1]; } //cout' pre[i]='pre[i]endl; } }矢量int result; result.reserve(n; intstart=Len[Len.size((-1] ); wile (开始!=int_min(result.push_back ) arr[start]; start=pre[start]; (intresult_len=(int ) result.size ); for(intI=result_Len-1; i0; I--; printf('%d ',result[i] ); printf(%d(n ),result[0]; }//[l,r ] binarysearchintbinary _ search (intl,int r,int target ) { int left=l,right=r; int result=-1; wile(L=R ) intmid=) LR ) 1; if(ARR[len[mid] ) target ) { l=mid 1; }else{ result=mid; r=mid-1; } }返回结果; }

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。