pta 習題集 5-5 最長連續遞增子序列 （dp）

給定一個順序存儲的線性表，請設計一個算法查找該線性表中最長的連續遞增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最長的遞增子序列為(3,4,6,8)。

輸入格式:

輸入第1行給出正整數（）；第2行給出個整數，其間以空格分隔。 

輸出格式:

輸入樣例：

15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10      

輸出樣例：

3 4 6 8      

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string>
#include <map>

using namespace std;
const int maxn=1e5;
int n;
int a[maxn+5];
int dp[maxn+5];
int search(int num,int l,int r)
{
  int mid;
  while(l<=r)
  {
    mid=(l+r)/2;
    if(num>dp[mid])
      l=mid+1;
    else
      r=mid-1;
  }
  return l;
}
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&a[i]);
  }
  memset(dp,0,sizeof(dp));
  dp[1]=1;
  for(int i=2;i<=n;i++)
  {
    if(a[i]>a[i-1])
      dp[i]=dp[i-1]+1;
    else
      dp[i]=1;
  }
  int max=0;
  int pos=0;
  for(int i=n;i>=1;i--)
  {
    if(max<=dp[i])
    {
      max=dp[i];
      pos=i;
    }
  }
  for(int i=pos-dp[pos]+1;i<=pos;i++)
  {
    if(i!=pos)
    printf("%d ",a[i]);
    else
      printf("%d\n",a[i]);
  }
  return 0;


}