1d配列の1の最長スジと初期位置を再帰的に見つける

Question

配列が与えられている場合。どのように再帰中の位置を追跡しますか？また、どのように最長のストリークを追跡しますか？

例：サイズが16 {1,0,1,1,1,0,0,0,1,1,0,0,1,1,0,1}の配列が与えられた 答えはaインデックス2の位置での長さ3のスジリック。

これは私が作った反復解です。それは完全に動作します。

int* iterative(int arr[],int length) 
{ 
    int temppos = 0; 
    int pos = 0; 
    int templen = 0; 
    int len = 0; 
    for(int i=0;i<length;i++) 
    { 
     if(arr[i]==1) 
     { 
      templen++; 
      if(templen>len) 
      { 
       len=templen; 
       pos=temppos; 
      } 
     } 
     else 
     { 
      templen=0; 
      temppos=i+1;; 
     } 
    } 
    static int x[2]= {pos,len}; 
    return x; 
} 

これは再帰的な解決策の私の擬似コード試みです。

int[] recursive(int[] array, int position, int streak) 
{ 
    if(array length is equal to 1 && arr[0]==1) 
    return result(position,streak) 
    else 
    leftsubarray(array/2) 
    rightsubarray(array/2+1) 
} 

与えられた反復解。私の基本的なケースと再帰的なステップはどうすればよいのですか？

Answer 1

これはあなたのproblem.A構造ansのC++における反復解法は、インデックスiとストリーク長streakを格納するために使用されています。

#include <iostream> 
using namespace std; 

typedef struct { 
    int i; 
    int streak; 
} ans; 

ans *a= new ans; 

void find_streak(int arr[],int i,int s) 
{ 
     if(arr[i]==1) 
     { 
      s++; 
     } 
     if(arr[i]==0 || i==15) //checking for end of streak or array 
     { 
      if(s>a->streak) //checking if the current streak is greater than max 
      { 
       a->streak=s; 
       a->i=i-s; 
      } 
      s=0; // initializing s to 0 for new streak 
     } 
     if(i+1<16) 
      find_streak(arr,i+1,s); 
     else 
      return; 
} 

int main() 
{ 
    int arr[]={1,0,1,1,1,0,0,0,1,1,0,0,1,1,1,1}; 
    a->i=0;a->streak=0; 
    find_streak(arr,0,0); 
    cout<<"Index: "<<a->i<<" streak: "<<a->streak<<endl; 
}