c - 从给定的由整数组成的数组中找到最大和的连续子数组

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

您的代码中有很多问题。

在 main 函数的第一个 for 循环中，您有:

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

• i 是全局变量且未初始化，因此您甚至没有正确地将元素扫描到元素中

• 您搞乱了您的 lsa 函数，即使上面的 for 循环已修复，该函数也不会产生正确的结果

• 代码的局限性之一是它仅适用于大小为 10 或更小的数组

<小时/>

我理解你想要找到最大连续数组的方式..正如你所说:

• the second loop runs from the first value keeping the value from the first loop fixed
• and the third loop is to get the sum of the sub array

我想说，与其进行第三个循环并使代码看起来很困惑，不如将其分解为另一个计算子数组之和的函数

<小时/>

解决方案:

在这里，我提供了一个适用于任何大小的数组的解决方案...只需使用 Dynamic array allocation

Note : lsa stands for 'largest contiguous sub-array'

• 这是主函数、函数声明和全局变量:

(说明在评论中给出)

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