整数からなる与えられた配列から最大の連続したサブアレイを見つける

Question

Cで最大の連続するサブアレイを見つけるコードを書いています。ロジックは私によればうまく見えますが、まだ出力が正しくありません。コードを見てください.3つ目のループでは、最初の値が固定された最初の値から3番目のループが実行され、3番目のループは、サブ配列の合計を取得します。

#include<stdio.h> 
int A[10],i,j; 
void lsa(int A[],int n) 
{ 
    int m,l,z,max=0,sum; 
    for(m=0;m<n;m++) 
    { 
     sum=0; 
     for(l=0;l<n;l++) 
     { 
      for(z=m;z<=l;z++) 
      { 
       if(m==l)     //maximum sum from a contiguous sub array 
       { 
       } 
       else 
       { 
        sum=A[z]+A[l]; 
        if(sum>max) 
        { 
         max=sum; 
         i=m; 
         j=l; 
        } 
       } 
      } 
     } 
    } 
} 
void main() 
{ 
    int n,p; 
    printf("enter size of array\n"); 
    scanf("%d",&n); 
    printf("enter array elements\n");  //creation of array 
    for(p=0;p<n;p++) 
     scanf("%d",&A[p]); 
     lsa(A,n); 
     printf("sub array is\n"); 
     for(p=i;p<j;p++) 
     { 
      printf("%d ",A[p]); 
     } 
} 

Answer 1

コードには多くの問題があります。

for(p=0;p<n;p++) 
    scanf("%d",&A[i]); 

• iは、グローバル変数と初期化されていないので、あなたも

正しく要素に要素をスキャンされていません。あなたが持っているmain関数の最初のforループでは、

• 上記のforループが固定されていても正しい結果が得られないlsa関数を使いこなしました

• し、コードの限界の一つは、それが唯一の大き10以下

---

の配列のために働くということです私はあなたが最大の連続配列を検索する方法を理解して..あなたが言ったように：

• 第二のループは、固定された第一のループからの値を保持する第一の値から実行
• 及び第3のループは、サブアレイ

の合計を得ることです、私は第3のループを作り、コードを作るのではなく、と言うだろう乱雑に見える、それは合計を計算し、別の関数にそれを壊し方が良いでしょうサブアレイの

---

ソリューション：私は、配列の任意のサイズのために機能するソリューションを提供してきました

ここでは...

：'最大の連続サブ配列'

• ここでは主な機能、関数宣言とグローバル変数だの略lsa：ちょうどDynamic array allocation

  注を使用して（コメント欄に記載されています）

  #include <stdio.h> 
  #include <stdlib.h> 
  
  //array pointer 
  int *array; 
  //size of lsa and its starting index value, same as i,j in your code 
  int lsa_size=1,lsa_start_index=0; 
  
  //function to find sum of sub array 
  int sum(int size_of_array, int start_index); 
  
  //the lsa function in your code 
  void lsaf(int *array,int size_of_array); 
  
  //main funtion 
  int main() 
  { 
      int size, index; 
  
      //scanning size of input array 
      printf("enter size of array\n"); 
      scanf("%d",&size); 
  
      //creates required amount of space for array 
      array=malloc(size*sizeof(int)); 
      if(array==NULL) //check if successfully created or not 
      { 
       //if not successful exit by returning 1 
       printf(" memory creation unsuccessful\n enter any key to exit : "); 
       exit(1); 
      } 
  
      //input of array elements 
      printf("enter array elements\n"); 
      for(index=0 ; index < size ; index++) 
       scanf("%d",&array[index]); 
  
      //function call ... function described below 
      lsaf(array,size); 
  
      //printing largest contiguous sub-array 
      printf("answer : "); 
      for(index=0 ; index < lsa_size ; index++) 
      { 
       printf("(%d)->",array[lsa_start_index]); 
       lsa_start_index++; 
      } 
  
      printf("*end*\n\n"); 
  
      //freeing allocated memory 
      free(array); 
  
      return 0; 
  }//main function 
  

  ---

  次に、lsa発見機能（Iはlsafとして命名しました）：

  void lsaf(int *array,int size_of_array) 
  { 
      int subarray_size,start_index,number_of_arrays; 
      int lsa_sum=sum(1,0);//initializing sum of lsa as first element 
      int subarray_sum; 
  
      for(subarray_size = 1; subarray_size <= size_of_array ; subarray_size++) 
      { 
       number_of_arrays = size_of_array - subarray_size +1; 
       for(start_index=0;start_index < number_of_arrays ; start_index++) 
       { 
        subarray_sum=sum(subarray_size,start_index); 
        if(subarray_sum >= lsa_sum) 
        { 
         //updating lsa size and starting index 
         lsa_sum=subarray_sum; 
         lsa_size=subarray_size; 
         lsa_start_index=start_index; 
        } 
       }//start_index loop 
      }//subarray_size loop 
  }//lsaf function 
  

  • 最初のループは、サブアレイのサイズ
  • 第二のループは、開始を決定する決定サブアレイのインデックス

  その代わりに第3のループで、Iは機能sum()を作成した今、このサブ配列の要素の和を計算：

  int sum(int size_of_array, int start_index) 
  { 
      int add=0,index; 
      for(index=0; index < size_of_array ; index++) 
      { 
       add+=array[start_index]; 
       start_index++; 
      } 
      return add; 
  }//sum function 
  

  • ので代わりに3つのループを作る、私は機能を作りました第3のループのために、私は私は疑問がコメントを経由して私に尋ねること自由に感じている場合...あなたは上記の機能を理解してほしい:)

    ---

    サブアレイ

  の合計を計算するためにそれを呼び出します

  だからあなたコードは次のようになり、すべて一緒に入れて：

  #include <stdio.h> 
  #include <stdlib.h> 
  
  //array pointer 
  int *array; 
  //size of lsa and its starting index value 
  int lsa_size=1,lsa_start_index=0; 
  
  //function to find sum of sub array 
  int sum(int size_of_array, int start_index); 
  
  //the lsa function 
  void lsaf(int *array,int size_of_array); 
  
  //main funtion 
  int main() 
  { 
      int size, index; 
  
      //scanning size of input array 
      printf("enter size of array\n"); 
      scanf("%d",&size); 
  
      //creates required amount of space for array 
      array=malloc(size*sizeof(int)); 
      if(array==NULL) //check if successfully created or not 
      { 
       //if not successful exit by returning 1 
       printf(" memory creation unsuccessful\n enter any key to exit : "); 
       exit(1); 
      } 
  
      //input of array elements 
      printf("enter array elements\n"); 
      for(index=0 ; index < size ; index++) 
       scanf("%d",&array[index]); 
  
      //function call 
      lsaf(array,size); 
  
      //printing largest contiguous sub-array 
      printf("answer : "); 
      for(index=0 ; index < lsa_size ; index++) 
      { 
       printf("(%d)->",array[lsa_start_index]); 
       lsa_start_index++; 
      } 
  
      printf("*end*\n\n"); 
  
      //freeing allocated memory 
      free(array); 
  
      return 0; 
  }//main function 
  
  
  int sum(int size_of_array, int start_index) 
  { 
      int add=0,index; 
      for(index=0; index < size_of_array ; index++) 
      { 
       add+=array[start_index]; 
       start_index++; 
      } 
      return add; 
  }//sum function 
  
  
  void lsaf(int *array,int size_of_array) 
  { 
      int subarray_size,start_index,number_of_arrays; 
      int lsa_sum=sum(1,0);//initializing sum of lsa as first element 
      int subarray_sum; 
  
      for(subarray_size = 1; subarray_size <= size_of_array ; subarray_size++) 
      { 
       number_of_arrays = size_of_array - subarray_size +1; 
       for(start_index=0;start_index < number_of_arrays ; start_index++) 
       { 
        subarray_sum=sum(subarray_size,start_index); 
        if(subarray_sum >= lsa_sum) 
        { 
         //updating lsa size and starting index 
         lsa_sum=subarray_sum; 
         lsa_size=subarray_size; 
         lsa_start_index=start_index; 
        } 
       }//start_index loop 
      }//subarray_size loop 
  }//lsaf function 
  

  ---

  サンプル入力と出力：

  enter size of array 
  6 
  enter array elements 
  1 
  -3 
  0 
  2 
  11 
  -90 
  answer : (0)->(2)->(11)->*end*