最大连续子数组问题-homework-01

1）先写我的 github 的介绍：

github 的域名：http://www.github.com/zhuifeng1022

登入 github 大概是下面的视图：

按照助教的方法：我已经建好了代码仓库：命名为 homework-01

代码仓库 homework-01 域名: http://www.github.com/zhuifeng1022/homework-01

2）我选择的教材：中文版代码大全 (第二版) 斯蒂夫·迈克康奈尔

以下是第一次作业：

　　我在课上想到的一种算法设计：

#include<stdio.h>

int max(int *a, int n)

{

    int i, j;

    int high, low;

    int max, sum;

    for (i = , max = ; i < n; i++)

        max = max + a[i];

    sum=;

    for (i = ; i < n; i++)

    {

        for(j = ;j < n; j++)

        {

            for(sum = , low = i, high = j; low <= high; low++)

            {

                sum = sum + a[low];

                if(sum > max)

                    max = sum;

            }

        }

    }

    return max;

}

int main()

{

    int a[];

    int i, n;

    FILE *in;

    in = fopen("data.in", "r");

    fscanf(in, "%d", &n);

    for (i = ; i < n; i++)

        fscanf(in, "%d", &a[i]);

    printf("%d\n", max(a, n));

    fclose(in);

    return ;

}

课后经过和同学的讨论，我又实现了另外一种O(n)的算法：

#include<stdio.h>

int max(int *a, int n)

{

    int i;

    int max, sum;

    for (i = ; i < n; i++)

    {

        if (a[i] < max)

            max = a[i];

    }

    sum = ;

    for (i = ; i < n; i++)

    {

        sum += a[i];

        if(sum > max)

            max = sum;

        if (sum < )

            sum = ;

    }

    return max;

}

int main()

{

    int a[];

    int i, n;

    FILE *in;

    in = fopen("data.in", "r");

    fscanf(in, "%d", &n);

    for (i = ; i < n; i++)

        fscanf(in, "%d", &a[i]);

    printf("%d\n", max(a, n));

    fclose(in);

}

巴特西

最大连续子数组问题-homework-01

最新文章

热门文章