從給定的數組中找到一個最大的連續子數組

Question

我正在編寫一個代碼來查找C中最大的連續子數組。根據我的邏輯看起來不錯，但輸出仍然不正確。請查看代碼。在第三個循環中，第二個循環從第一個值開始運行，第一個循環的值從第一個循環固定，第三個循環用於獲取子陣列的總和。請查看代碼

#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環main功能，您有：

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

• i是全局變量和未初始化，所以你甚至不掃描元素融入你的元素正確

• 你已經搞亂了你的lsa函數，即使上面的for循環是固定的也不會產生正確的結果

  0你的代碼的限制

• ，一個是它僅適用於大小10以下

---

我知道你想找到最大的連續陣列..如你所說的方式排列：

• 第二環路從所述第一值從固定在所述第一環保持值運行
• ，第三環是讓子陣列的總和

我想說的不是使第三循環，使代碼顯得凌亂，最好將它分解成計算和其他功能子陣列的

---

解決方案：

在這裏，我提供了工作陣列的任何大小的一個解決方案...剛開始使用Dynamic array allocation

注意：lsa代表'最大的連續子陣列'

• 這裏的主要功能，函數聲明和全局變量：

（說明在評論中給出）現在

#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發現功能（我把它命名爲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 

• 第一循環決定子數組的大小
秒循環決定啓動子陣列的索引

和現在，而不是第三環，我已經創建的函數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個迴路，我做了一個函數第三循環，我把它計算子陣列

我希望你明白上述功能......如果任何疑問請隨時通過評論:)

---

問我的總和

所以把所有在一起的代碼將是：

#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*