算法第二章上机实践报告

实践题目名称

最大子列和问题

问题描述

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

算法描述

如图，采用分治法和二分递归来出目标子区间，将目标的子段分为三种可能性

• 横跨mid两端
• 只在mid左边
• 只在mid右边

每次选取一个mid，求出mid向左的最大连续子序列和与mid向右的最大连续子序列和，相加得到跨过mid两端的最大子段和。将其与左边和右边的最大字段和进行比较，选出三者中最大的那个。而左边和右边的最大子段和则是通过递归，将其再次看成一个可以划分mid的子段求出其范围的最大子段得出。

通过递归每次得出最大的子段和，递归到最后出口就是整个数列最大的子段和。

复杂度分析

• 时间复杂度

由于是分治法，通过二分每次得出2个规模为原来二分之一的问题来求解，所以可以写出下列表达式

T(n) = 2T(n/2)+O(n)

通过主定理可以得出d=log_ba=log₂2=1

所以时间复杂度为O(nlogn)

• 空间复杂度

由于这个算法都是在原数组上进行操作，所以算法的空间复杂度为O(1)

心得体会

一开始对这个算法存在疑惑，认为这种方法不能考虑周全，可能存在欠考虑的情况。后来认真理解清楚后才发现这种分治法对问题进行了很好的规模与情况分类，也做到了考虑到所有情况，不禁感到精妙。

所以还是要加强自己在写代码前对算法的理解程度，想清楚了再开始写，才不会中间出现很多的bug，同时搭档2人之间也要交流清楚，才能提高效率和精确度。

算法第二章上机实践报告

原文：https://www.cnblogs.com/ccqstark/p/13769991.html