洛谷[P1420]最長連号

題目傳送門OvO

題目描述

輸入n個正整數，（1<=n<=10000),要求輸出最長的連号的長度。（連号指從小到大連續自然數）

輸入輸出格式

輸入格式：

第一行，一個數n;

第二行，n個正整數，之間用空格隔開。

輸出格式：

一個數，最長連号的個數。

很多同學都把這題想的很複雜，用遞歸做。

但是這道題n<=10000,明明o(n)可以跑過，為什麼這麼複雜呢

獻上一份不複雜的代碼：

#include<bits/stdc++.h>       //神奇頭檔案不用解釋
#define INF 10234567
using namespace std;
int main()                                //不用遞歸
{
    int n,s[1001],ans=0,max=-INF;            //n表示輸入有n個正整數，ans呢待會解釋，max可以不用想了，一定是最後的答案,為什麼被指派為-INF下面解釋
    cin>>n;                                               //輸入n
    for(int i=1;i<=n;i++)                           //循環了n次
        cin>>s[i];                                    //将數存進s數組裡，其實也可以不存，這樣會更好了解
    for(int i=1;i<=n;i++)                          //仍舊循環n次，對n個數進行處理
    {                                                         //以下以樣例為例來解釋代碼：10\n3 5 6 2 3 4 5 6 8 9
        if(s[i+1]-s[i]==1)ans++;             //i從1到n，當i=1時s[i+1]表示3後面一個數，即為5，如果5-3==1，就說明3，5是連号，這裡顯然不是。如果是就将ans++，是以這裡的ans隻是為了臨時存一下連号的個數，以此類推。
        else ans=0;                                  //一旦發現了一次不連号，就将臨時存儲的資料變為0
        if(ans>max)max=ans;                 //将max賦為-INF的原因是為了找到ans中的最大值，達到題目目的
    }
    cout<<++max;                                  //最後輸出最大值
}
           

然後我嘗試用遞歸做了一次，TLE……

是以，我們需要用dp來優化

來人！上代碼！

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n+1],dp[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int maxn=0;
    for(int i=n;i>0;i--)
    {
        if(i==n)
        {
            dp[i]=1;
        }
        else
        {
            if(a[i+1]-1==a[i])
            {
                dp[i]=dp[i+1]+1;
            }
            else
            {
                dp[i]=1;
            }
        }
        maxn=max(dp[i],maxn);
    }
    cout<<maxn;
    return 0;
}