image.png
int MAX[N]={0};
// 记录到该点的最长子序列长度
int son[N]={0};
// 记录该点的最长子序列的上一个点的位置
for(i=0;i<counts;i++){
MAX[i]=1;
// 所有点i的子序列都大于等于1
}
// 处理MAX数组
for(i=1;i<counts;i++){
// 从1开始，因为0不用遍历
for(j=0;j<i;j++){
// 从0开始，但是在i-1的时候止步
if(a[i]>a[j]){
if(MAX[j]+1>MAX[i]){
son[i]=j;
// 记录上一个节点的位置
MAX[i]=MAX[j]+1;
}
}
}
}
记录子序列的值对应的数组下标(只记录其中一个):
void print(){
int i,j;
int output[N]={0};
for(i=counts-1;i>=0;i--){
int start=0;
int next=son[i];
output[start]=i;
while(next!=son[next]){
output[++start]=next;
next=son[next];
}
output[++start]=next;
// 最后一个节点不要忘了
if(start==largest-1){
// start长度值小1
for(j=0;j<largest;j++){
cout<<output[j]<<"-->";
}
cout<<endl;
}
}
}
- 求路径：
#include <bits/stdc++.h>
using namespace std;
#define N 10000
int points,edges;
int MAX[N]={0};
// 以该节点为端点的不下降子序列的最大长度
int num[N]={0};
// 存放输入
int son[N]={0};
// 存放上一级节点
vector<int>v;
int findstart(int end,int maxlength){
int i,j;
int start=end;
cout<<num[end]<<">>";
while(start>=0){
// 当start==son[start]，说明到达了子串的起点，break
if(start!=son[start]){
start=son[start];
cout<<num[start]<<">>";
}
else{
break;
}
}
cout<<endl;
return start;
}
int main(){
int i=0,j,input,length=0;
scanf("%d",&length);
for(i=0;i<length;i++){
scanf("%d",&input);
num[i]=input;
MAX[i]=1;
son[i]=i;
}
length=i;
MAX[0]=1;
// 以i为子序列的终点，遍历所有num比它小的MAX
// 得到max(MAX[i],MAX[j]+1)作为MAX[i]的最终值
for(i=1;i<length;i++) {
for(j=0;j<i;j++){
if(num[j]<num[i]){
if(MAX[i]<MAX[j]+1){
// j更适合加入串
MAX[i]=MAX[j]+1;
// 记录串中上一个节点的坐标
son[i]=j;
}
}
}
}
// 从MAX[i]中找出最长子串的长度
int maxlength=0;
int end=-1;
int start=0;
for(i=0;i<length;i++){
if(MAX[i]>maxlength){
maxlength=MAX[i];
end=i;
}
}
cout<<"maxlength:"<<maxlength<<endl;
cout<<"end:"<<end+1<<endl;
// 利用end和maxlength沿着son[]一路补全整个串
start=findstart(end,maxlength);
cout<<"start:"<<start+1<<endl;
}
/*
10
1 3 5 4 2 3 6 4 2 7
*/
最佳方法：
用map存长度为1->max对应的节点index，这个index满足其对应nums[index]<nums[i]，且理论上只需要保留最多一个（也可能没有）。因为1到max之间肯定是连续的，那么只要从max到1遍历，取末尾元素比较相对大小即可判断能不能作为该点后续。最后返回max即可。
- python map版：{length:index}
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp=[1 for i in range(len(nums))]
d={}
d[1]=0
for i in range(1,len(nums)):
itr=list(d.keys())
for j in range(len(itr)-1,-1,-1):
if itr[j] in d:
if nums[d[itr[j]]]<nums[i]:
dp[i]=itr[j]+1
break
if dp[i] not in d:
d[dp[i]]=i
else:
if nums[d[dp[i]]]>nums[i]:
d[dp[i]]=i
return list(d.keys())[-1]
可惜map是封装好的红黑树无法对最优长度进行二分查找优化。
- 从一个角度想，如果map的每个key都连续，那么就可以用数组存，如果每个i都基于
[0,i-1]的最优解，那么对应的最优解index对应的高度肯定也是个有序数组，也就可以引入二分查找第一个小于target高度的点了。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
len2index=[]
len2index.append(0)
for i in range(1,len(nums)):
left=0
right=len(len2index)-1
while(left<=right):
middle=(left+right)//2
if nums[len2index[middle]]<nums[i]:
left=middle+1
else:
right=middle-1
if right<0:
if(nums[len2index[0]])>nums[i]:
len2index[0]=i
else:
if nums[len2index[right]]<nums[i]:
if right+1+1>len(len2index):
len2index.append(i)
else:
len2index[right+1]=i
return len(len2index)
