**本博客内容根据慕课浙大数据结构1.3课什么是算法？如果对博客中的算法有任何疑问，欢迎指正**问题：子序列问题有一个序列N，其中包含[A1,....AN]个整数，求解得到最大的连续子序列和.例子：N:[1,2,-1]几个连续的子序列：[1][2][-1][1,2][2,-1][1,2,-1]最大的连续子序列是3。面对这个问题，最暴力的方法就是穷举所有的子序列，然后取其中最大的子序列和。C1循环方法：defget_max_sequence_sum(nums:list)->int:length=len(nums)this_sum=max_sum=0#遍历子序列的起始索引forfirst_indexinrange(length):#遍历子序列的结束索引forend_indexinrange(first_index,length):#计算当前子序列和fornuminnums[first_index:end_index+1]:this_sum+=nummax_sum=this_sumifthis_sum>max_sumelsemax_sumthis_sum=0returnmax_sumforthisalgorithm,计算过程中进行了3次循环，T(n)=n^3显然可以发现，在计算子序列和的时候，可以通过前一个子序列和下一个整数相加得到新的子序列和C2循环的方法2.0defget_max_sequence_sum(nums:list)->int:length=len(nums)this_sum=max_sum=0#遍历first_indexinrange(length)子序列的起始索引:#遍历end_indexin子序列的结束索引范围（第一个索引，长度）：#当前子序列的和是前一个子序列加上当前整数的和this_sum+=nums[end_index]max_sum=this_sumifthis_sum>max_sumelsemax_sumthis_sum=0returnmax_sumpassedforthesubsequencesum优化后每次计算子序列和的周期可以减少，T(n)=n^2减少周期的优化后，我们可以进一步使用分治的思想来优化这个算法对于最大子序列和问题，我们可以将问题分解为将序列按中间分为左右两个序列，然后分别计算左边子序列的最大子序列和和右边子序列的最大子序列，以及得到的最大子序列从中间向两边扫描序列和第一步得到左右序列[4,-3,5,2],[-1,2,6,2]第二步计算左边的最大子序列和右序列，继续将左序列分解为[4,-1],[5,2]，将左序列和右序列继续分解为[4]，[-1]；[5],[2]得到左右序列和最大和为4,左右序列最大和为5然后左边序列[4,-3,｜5,2]从除线到两边，最大子序列和为6，所以左边序列的最大子序列和为6，以此类推，右边序列的最大子序列和为8步骤3：初始序列从最大序列和开始向左右两侧扫描的分界线的个数为11。第四步：比较三部分之和，得到最大值11。治愈法的思路是不断分解问题，然后组合子问题的结果得到最终结果。因此，我们可以得到第三个算法C3分而治之defget_max_sequence_sum(nums:list)->int:length=len(nums)middle_index=length//2middle_to_left_this_sequence_sum=middle_to_left_max_sequence_sum=0middle_to_right_this_sequence_sum=middle_to_right_max_sequence_sum=0#递归终止iflength==0:return0iflength==1:returnnums[0]ifnums[0]>0else0#通过递归得到左子序列和右子序列的最大子序列和left_max_sequence_sum=get_max_sequence_sum(nums[:middle_index])right_max_sequence_sum=get_max_sequence_sum(nums[middle_index:])#计算从中间向两边扫描得到的最大子序列和#从中间向左扫描得到最大值fornuminnums[:middle_index]:middle_to_left_this_sequence_sum+=nummiddle_to_left_max_sequence_sum=middle_to_left_this_sequence_middle_to_left_this_sequence_sum>middle_to_left_max_sequence_sumelse\middle_to_left_max_sequence_sum#从中间往右边扫描得到最大的fornuminnums[middle_index:]:middle_to_right_this_sequence_sum+=nummiddle_to_right_max_sequence_sum=middle_to_right_this_sequence_sumif\middle_to_right_this_sequence_sum>middle_to_right_max_sequence_sumelse\middle_to_right_max_sequence_summiddle_max_sequence_sum=middle_to_left_max_sequence_sum+middle_to_right_max_sequence_sumreturnmax([left_max_sequence_sum,right_max_sequence_sum,middle_max_sequence_sum])使用这种分而治之的方法，问题将be每次分解成一半，然后扫描整个序列，所以最后T(n)=nlogn一般来说，使用分而治之的方法，我们已经可以得到一个相对优化的解，但是对于一些问题，我们还可以通过更微妙的数学思想来优化问题。比如对于子序列和的计算，因为它是一个连续的子序列，如果得到的某个子序列的和<0，那么我们就可以完全舍弃这个子序列，直接从下一个数开始继续，得到一个新的子序列和。这种处理方式也称为“在线问题处理”。C4在线处理方法defget_max_sequence_sum_4(nums:list)->int:this_sum=max_sum=0fornuminnums:this_sum+=nummax_sum=this_sumifthis_sum>max_sumelsemax_sum#如果当前子序列的和<0，丢弃thissubsequence直接Sequenceifthis_sum<0:this_sum=0returnmax_sum我们可以清楚的看到这个算法的平均时间复杂度是n。参考Mooc-数据结构
