PAT复杂度

01-复杂度1. 最大子列和问题

给定K个整数组成的序列{ N1, N2, ..., NK },“连续子列”被定义为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。

输入格式:

输入第1行给出正整数 K (<= 100000);第2行给出K个整数,其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数,则输出0。

输入样例:
6
-2 11 -4 13 -5 -2
输出样例:
20 

分析:最自然的想法就是枚举始终位置,如下程序,但是复杂度O(n^3),对于某些测试点超时。

#include<stdio.h> #define MAXN 100000 int arr[MAXN+10]; int main(void)
{ int i, j, k, n, thisSum, maxSum = 0;
    
    scanf("%d", &n); for(i = 0; i < n; i++)
        scanf("%d", &arr[i]); for(i = 0; i < n; i++) for(j = i; j < n; j++)
        {
            thisSum = 0; for(k = i; k <= j; k++)
                thisSum += arr[k]; if(thisSum > maxSum)
                maxSum = thisSum;
        }
    printf("%d\n", maxSum); return 0;
}

既然超时了,就想办法优化一下呗,容易观察到,对于某个固定的i, 变化的j(从i 开始),上面的程序反复计算从下标i 到下标j 的和,这是没有必要的,存在多次重复计算,因此可以如下改写:复杂度O(n^2)。

#include<stdio.h> #define MAXN 100000 int arr[MAXN+10]; int main(void)
{ int i, j, n, thisSum, maxSum = 0;
    
    scanf("%d", &n); for(i = 0; i < n; i++)
        scanf("%d", &arr[i]); for(i = 0; i < n; i++)
    {
        thisSum = 0; for(j = i; j < n; j++)
        {
            thisSum += arr[j]; if(thisSum > maxSum)
                maxSum = thisSum;
        }
    }
    
    printf("%d\n", maxSum); return 0;
}

看到这里,你可能想到了求序列的前n 项和来解决这个问题,我们令Si 为序列的前i 项(包括i)和。那么下标从i 到j 的连续子序列和为Ai + Ai+1 + ... + Aj = Sj - Si-1
注意到,前面我故意模糊了i 的取值,是因为我们得借助表达式Sj - Si-1 来定界。显然,为了得到我们想要的结果,Sj - Si-1 必须的遍历每一个子序列,得到界限:1 <= i <= n, i ≤ j ≤ n。即S0 = 0,这需要在程序中体现出来,不然肯定WA。复杂度仍然是O(n^2),程序如下:

#include<stdio.h> #define MAXN 100000 int arr[MAXN+10]; int main(void)
{ int i, j, n, thisSum, maxSum = 0;
    
    scanf("%d", &n); for(i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    
    arr[0] = 0; for(i = 2; i <= n; i++)
        arr[i] += arr[i-1]; // 递推前n项和 for(i = 1; i <= n; i++) for(j = i; j <= n; j++)
        {
            thisSum = arr[j] - arr[i-1]; if(thisSum > maxSum)
                maxSum = thisSum;
        }
    printf("%d\n", maxSum); return 0;
}

难道我们就摆脱不了n^2 的噩梦?怪姥姥告诉我们说:想成为一个优秀的Coder,看到n^2 就得下意识的想到能不能把n^2 降阶,什么nlogn 啦,甚至n 什么的。考虑到二分时复杂度为logn,因此我们可以来个移花接木,借用其思想,换句话说,可以用分治法。分:二分,递归。治:治理。如果采用二分的思想的话,考虑连续子序列最大和可能出现的位置有三种,二分的左侧、右侧或是跨越两者边界的情况,因此有:

#include<stdio.h> #define MAXN 100000 int maxSeqSum(int arr[], int low, int high); int maxOfThree(int a, int b, int c); int arr[MAXN+10]; int main(void)
{ int i, n;
    
    scanf("%d", &n); for(i = 0; i < n; i++)
        scanf("%d", &arr[i]); 
    
    printf("%d\n", maxSeqSum(arr, 0, n-1)); return 0;
} int maxSeqSum(int arr[], int low, int high) // 左闭右闭区间 { int i, mid, max1, max2, thisSum, maxLeftSum, maxRightSum; // printf("%d %d\n", low, high); 测试用的语句,正如下面优先级那里说的,不用该行捕获输出的话,输入完数据程序就退出了,怎生死的都不知道. if(low == high) return arr[low];
        
    mid = low + ((high-low) >> 1); // 优先级+bigger than>>,这个错误不止出现一次了Orz,如果不加括号的话,由于无限递归导致堆栈溢出将发生段错误 max1 = maxSeqSum(arr, low, mid);
    max2 = maxSeqSum(arr, mid+1, high);
    
    thisSum = maxLeftSum = 0; for(i = mid; i >= low; i--)
    {
        thisSum += arr[i]; if(thisSum > maxLeftSum)
            maxLeftSum = thisSum;
    }
    thisSum = maxRightSum = 0; for(i = mid+1; i <= high; i++)
    {
        thisSum += arr[i]; if(thisSum > maxRightSum)
            maxRightSum = thisSum;
    } return maxOfThree(max1, max2, maxLeftSum+maxRightSum);
} int maxOfThree(int a, int b, int c)
{ int max = a; if(b > max)
        max = b; if(c > max)
        max = c; return max;
}

有没有发现,代码风格我采用的Java 的。编码的时候很慢,因为我经常琢磨怎么命名,下划线分隔的、所有首字母大写的、瞎搞的不一而足。最终还是采用了Java 风格的变量命名法。既然刚才提到nlogn 了,我们就来证明下,该程序的时间复杂度为O(nlogn)。首先,此程序的时间复杂度显然和输入规模有关,因此我们令对n 的输入规模耗时为T(n)。那么显然有T(n) = 2T(n/2) + n; 即T(n) = 2T(n/2) + n = 2[2T(n/4) + n/2] + n = ... 不断迭代下去容易得到形式T(n) = 2 k T(n/2k) + kn。令2^k = n,则T(n) = n + nlogn = O(nlogn)。[注:这里只对n 是2 的幂做了讨论,不过其他的值和该方法分析的结果不会有偏差,我们可以规约吗:)]。然而O(nlogn)就是时间优化的极限了吗?很遗憾,不是的,还有更强的,下面是世间复杂度为O(n)的暴强版:

#include<stdio.h> #define MAXN 100000 int arr[MAXN+10]; int main(void)
{ int i, n, thisSum, maxSum = 0;
    
    scanf("%d", &n); for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    
    thisSum = 0; for(i = 0; i < n; i++)
    {
        thisSum += arr[i]; if(thisSum > maxSum)
            maxSum = thisSum; if(thisSum < 0)
            thisSum = 0;
    }
    
    printf("%d\n", maxSum); return 0;
}

其思想很巧妙,就是thisSum一旦小于零,就重置其值为0。因为用一个序列和小于零的序列在拼接后面的数是没有意义的,它永远不会是最大的。最后,还有更快的吗?不好意思,没有了,这是最快的了,没有更快的了,因为该算法是在线的,想要求最大和至少得读一遍数据吧,而光读数据就得花费O(n) 的时间,没有人会认为还没扫描完数据就能求出最大和吧。

上面贴了五个程序,为了直观的看到它们时间复杂度的不同,感悟思维的魅力,我把各测试点的用时记录在下面的表格里:

测试点 程序1用时(ms) 程序2 程序3 程序4 程序5
0 1 1 1 1 1
1 1 1 1 1 1
2 126 1 1 1 1
3 TLE 50 50 2 2
4 TLE 4854 4857 12 9
01-复杂度2. Maximum Subsequence Sum (25)

Given a sequence of K integers { N1, N2, ..., NK }. A continuous subsequence is defined to be { Ni, Ni+1, ..., Nj } where 1 <= i <= j <= K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (<= 10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4 

分析:该题目是04年浙大考研复试真题,是第一个题目的简单的变形,对于上面五个程序中时间复杂度为O(n) 的程序很好改写,对于O(nlogn) 的那个略难。

改写O(n):

#include<stdio.h> #define MAXN 100000 int arr[MAXN+10]; int main(void)
{ int n, i, thisSum, maxSum, begin, end, index;
    
    scanf("%d", &n); for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    
    thisSum = maxSum = index = 0; for(i = 0; i < n; i++)
    {
        thisSum += arr[i]; if(thisSum > maxSum)
        {
            maxSum = thisSum;
            begin = index;
            end = i;
        } if(thisSum < 0)
        {
            thisSum = 0;
            index = i+1;
        }
    } if(maxSum == 0)
    { for(i = 0; i < n; i++)
        { if(arr[i] == 0) break;
        } if(i == n) // 所有元素都是负数 printf("%d %d %d\n", 0, arr[0], arr[n-1]); else printf("0 0 0\n");
    } else printf("%d %d %d\n", maxSum, arr[begin], arr[end]); return 0;
}

改写O(nlogn):

#include<stdio.h> #define MAXN 100000 int MaxSeqSum(int arr[], int low, int high); int MaxOfThree(int a, int b, int c); int arr[MAXN+10]; int G_MAX = 0; int G_LeftIndex = 0; int G_RightIndex = 0; int main(void)
{ int i, n, ans;
    
    scanf("%d", &n); for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);
         
    ans = MaxSeqSum(arr, 0, n-1);
    printf("%d", ans); if(ans == 0)
    { for(i = 0; i < n; i++) if(arr[i] == 0) break; if(i == n)
            printf(" %d %d", arr[0], arr[n-1]); else printf(" %d %d", 0, 0);
    } else printf(" %d %d", arr[G_LeftIndex], arr[G_RightIndex]); return 0;
} int MaxSeqSum(int arr[], int low, int high) // 左闭右闭区间 { int i, leftBoundIndex, rightBoundIndex, mid; int max1, max2, max3, thisSum, maxLeftSum, maxRightSum, localMax; if(low == high)
    { if(arr[low] <= 0) return 0; else return arr[low];
    }
        
    mid = low + ((high-low) >> 1); // 注意优先级,这里栽了好几次了Orz... max1 = MaxSeqSum(arr, low, mid);
    max2 = MaxSeqSum(arr, mid+1, high);
    
    thisSum = maxLeftSum = 0; for(i = mid; i >= low; i--)
    {
        thisSum += arr[i]; if(thisSum > maxLeftSum)
        {
            maxLeftSum = thisSum;
            leftBoundIndex = i;
        }
    }
    thisSum = maxRightSum = 0; for(i = mid+1; i <= high; i++)
    {
        thisSum += arr[i]; if(thisSum > maxRightSum)
        {
            maxRightSum = thisSum;
            rightBoundIndex = i;
        }
    }
    
    max3 = maxLeftSum + maxRightSum;
    localMax = MaxOfThree(max1, max2, max3); if(G_MAX < localMax)
    {
        G_MAX = localMax; if(max1 == G_MAX)
        {
            G_LeftIndex = G_RightIndex = low;
        } else if(max3 == G_MAX)
        { if(max3 == max2) // 左边界未初始化,为垃圾值,至于右边界的问题在第一个if里已经得到了处理 G_LeftIndex = rightBoundIndex; else G_LeftIndex = leftBoundIndex;

            G_RightIndex = rightBoundIndex;
        } else {
            G_LeftIndex = G_RightIndex = high;
        }
    } // printf("%d %d\n", low, high); // test // printf("%d %d\n", G_LeftIndex, G_RightIndex);  return localMax;
} int MaxOfThree(int a, int b, int c)
{ int max = a; if(b > max)
        max = b; if(c > max)
        max = c; return max;
} 


全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 18:05
哈哈哈哈哈感觉朋友找工作的已经疯掉了,直接上图
码农索隆:真老板娘:“我嘞个去,这不我当年的套路吗
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
北漂的牛马人:211佬,包进的,可能是系统问题
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务