longest.cpp

来自「给出一个由非0整数组成的序列a1,a2,…,an, 设计递归算法求其中由同号整数」· C++ 代码 · 共 36 行

//最长同号连续段
#include "iostream.h"
#include "stdio.h"
#define N 1001
int ls(int start, int n, int a[]); 
int main()
{ int k,n,i,j,len,a[N];
  cin>>k;
  for (i=1; i<=k; i++)
  {
	  cin>>n; 
	  for (j=1;j<=n;j++) cin>>a[j];
	  len=ls(1,n,a);
	  cout<<len<<endl;
  }
  return 1;
}
int ls(int start, int n, int a[])
{
	int length=0,sign,m;
    if (start<=n) 
	{   if (a[start]>0) sign=1; else sign=-1;
        start++; length++;
	    while(start<=n)
		{ 
		     if (a[start]*sign>0) {length++;start++;}
	         else 
			 { 
			    m=ls(start,n,a);
		        if (m>length) length=m;
                return length;
			 }
		}
	}
    return length;
}