算法第3章上机实践报告

一、 实践题目：7-2 最大字段和

二、 问题描述：

给定n个整数（可能为负数）组成的序列a[1], a[2], a[3]...,a[n]，求该序列和如a[i] + a[i + 1] + .... + a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。

要求算法的时间复杂度为O(n)。

三、 算法描述

在除去所有数都是负数的特殊情况后，从0开始遍历数组，每向前一个数，得到第0~i个子序列，以及一个极大字段和（分为两种情况1.将第i-1的最大字段和加上第i个数，得到第0~i子序列的极大字段和。2.将第i个数直接作为极大字段和。比较1、2两种情况的大小求出0~i的极大字段和），将极大字段和与一直所记录的最大字段和进行比较，最终得到最大字段和并输出。

四、 算法实践及空间复杂度分析（含分析过程）

1．算法实践

#include 
     
      int n, tmp = 0, sum = 0;int a[10005];int main(){    scanf("%d", &n);    int f = 0;    for (int i = 1; i <= n; i++) {        scanf("%d", &a[i]);        if (a[i] >= 0)            f = 1;    }    if (f == 0) {        printf("0\n");        return 0;    }    // 全部都为负数         for (int i = 1; i <= n; i++) {        if (tmp > 0){            // 0~i-1的极大字段和为正数            tmp += a[i];        }    // 情况一：0~i-1的极大字段和 + a[i]         else {            tmp = a[i];        }    //  情况二：极大字段和 = a[i]         if (tmp > sum){            sum = tmp;        }        }    // 有一点tricky，此方法与本题比较相关         printf("%d\n", sum);    return 0;}
     

2．空间复杂度分析：O(n)

五、 心得体会（含本次实践收获及疑惑进行总结）

1．在上机课讲解队友代码的时候不要过于紧张，要看清想清题目再回答问题。

2．认真审题，及早发现特殊样例。

3．想清楚题目，举例确定算法。

六、 参考链接

1．

2．

3．