P1567 统计天数

杨鹏伟

发布于 2020-09-10 22:09:17

4520

文章被收录于专栏：ypwypw

题意：求最长连续串的长度。

思路：一开始我想的是两个for不断跟新维护。然后不断跟新得到最大值。

但这样写超时了·~

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;

ll a[1000006];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ll k ;
	ll ans = -inf;
	for(int i=1;i<=n;i++){
		k = 0;
		int res = i;
		while(a[res]<a[res+1]&&res+1<=n){
			k++;
			res++;	
		}
		//cout<<k<<"  ---";
		ans = max(ans,k+1);
			
	}
	cout<<ans<<endl;
	return 0;
}

然后我想着该如何优化呢，就是将两个for变成一个for,然后就是这个时候得用的多余得空间换取时间，所以在开一个数组，将每次得值都记录，然后在遍历得到最大值

#include<bits/stdc++.h>
#define N 10000000
int main(){
        int k=1, n=0,max,a[N],b[N];             
        scanf("%d", &n); 
        for(int i=0; i<n; i++)
            scanf("%d", &a[i]);
        for(int i=0; i<n; i++){
            if(a[i]<a[i+1]){
                k++;
                b[i]=k; 
            }
            else{
                k=1;
                b[i]=k;
            }
        }
    max=b[1];
    for(int i=0; i<n; i++)
        if(max<b[i])
          max=b[i];

        printf("%d\n",max);
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/02/19 ，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历