原题传送门

思路


尽管是一道入门级别的水题,n<10000,暴力就可以过,但若n<100000000,就需要我们伟大的动态规划出场了QAQ。

运用DP,我做出了O(n)的算法。

dp[i]表示从上一个连号被中断的数字的下一个到第i个的连号长度。

有点难理解哈,看状态转移方程吧:
dp[i]=dp[i-1]+1(no[i]=no[i-1]+1)
dp[i]=1 (no[i]≠no[i-1]+1)
(no[]表示输入的数组)

我们还需要一个tans来记录当前连号长度,若tans>ans,则将ans设置为tans,若连号中断,则将tans重置为1。

剩下的就是水代码了QAQ.

Code


#include<iostream>
#include<cstdio>

using namespace std;

const int MAX=10001;
int dp[MAX],no[MAX];
int n,ans=1,tans;

int main()
{
    //初始化
    dp[1]=1;
    //freopen("testdata(3).txt","r",stdin);
    //读入
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>no[i];
    }

    //装叉走起
    for(int i=2;i<=n;i++)
    {
        if(no[i]==no[i-1]+1)
        {
            dp[i]=dp[i-1]+1;
            tans++;
            if(tans>ans)
            {
                ans=tans;
            }
        }
        else
        {
            dp[i]=1;
            tans=1;
        }
    }

    //输出
    cout<<ans<<endl;
    return 0;
}
02-01 02:07