目录一、题目二、算法求解1、蛮力算法伪代码 算法分析程序2、分治策略伪代码算法分析程序3、动态规划算法伪代码算法分析程序一、题目设A=是n个整数的序列，称为该序列的连续子序列，其中1称为A的子段和：例如，A=，那么它的子段和如下：长度为1的子段和有：-2,11,-4,13,-5,-2长度为2的子段和有：9,7,9,8,-7长度为3的子段和有：5,20,4,6长度为4的子段和有：18,15,2长度为5的子段和有：13,13长度为6的子段和有：11其中的最大子段和为：11-4+13=20则最大子段和问题为：给定n个整数的序列A=，求二、算法求解1、蛮力算法通过枚举A的所有连续子序列并且求和，通过比

分治法\(O(n\log{n})\)按照“分而治之”的思想，将整个数据区间从中间一分为二，这样我们就将求整个区间的最大子列和转换为求小区间的最大子列和。设区间左端为left，区间右端为right，区间中间为middle。思考一下，求小区间的子列和一共存在一下三种情况：求左区间的最大子列和：[left,middle]求右区间的最大子列和：[middle+1,right]求从左区间横跨至右区间的最大子列和代码实现#include#includeusingnamespacestd;intK;constintN=1e7;intarr[N];/*从左区间横跨至右区间的情况*/intgetSpecialS

分治法\(O(n\log{n})\)按照“分而治之”的思想，将整个数据区间从中间一分为二，这样我们就将求整个区间的最大子列和转换为求小区间的最大子列和。设区间左端为left，区间右端为right，区间中间为middle。思考一下，求小区间的子列和一共存在一下三种情况：求左区间的最大子列和：[left,middle]求右区间的最大子列和：[middle+1,right]求从左区间横跨至右区间的最大子列和代码实现#include#includeusingnamespacestd;intK;constintN=1e7;intarr[N];/*从左区间横跨至右区间的情况*/intgetSpecialS