saviour L2 2017-05-29 05:57:41 基本概念
470 2

“数据结构(新版)”实验报告

基本概念
//Version 1.0
int max_sum(int* a, size_t sz) {
    int max = 0, sum = 0, maxOfAll = 0;    
    for (int j = 0; j < sz; ++j) {//通过两次循环来遍历所有子序列和
        for (int i = j; i < sz; ++i) {
            sum += a[i];
            if (sum > max)
                max = sum;
        }
        if (max > maxOfAll)
            maxOfAll = max;
        sum = 0;
    }
    return maxOfAll;
}
copy
//Version 2.0
int max_sum(int* a, size_t sz) {
    int max = 0, sum = 0;
        for (int i = 0; i < sz; ++i) {
            sum += a[i];
            if (sum > max)
                max = sum;
            if (sum < 0)// 和为负则抛弃其和,重新计算
                max = 0;
        }
    return max;
}
copy
   刚开始的想法很直观,就是遍历所有的子序列和,然后求最大值。跑了几遍发现这样效率很低,算法时间复杂度为O(n!)。后来看了别人的实验报告, 原来可以通过循环中判断和的值是否为负,如果为负则把子序列和重置巧妙地减小复杂度,改过之后的函数Version2 中所示,此时算法时间复杂度为O(n),可见有很大的提升。
copy
最新评论
回复

那个,是sum小于0的时候令sum等于0吧?而且判断应该提到前面

2017-06-18 23:10:45
回复

第一种算法复杂度算错了,执行次数为 n + (n-1) + (n-2) + …… + 1 = n(n+1)/2 , 所以最后复杂度为O(n^2)

2017-05-30 23:07:41
回复