* 最长不下降子序列

---

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
*/