《最大子段和问题.ppt》由会员分享，可在线阅读，更多相关《最大子段和问题.ppt（18页珍藏版）》请在三一文库上搜索。
1、最大子段和问题,制作：七(10)班王晶晶,【题目描述】 给定一组数列，求连续子段和最大值。 【输入格式】 第一行一个数n，表示数列长度（n=100000） 第二行，n个数，表示一个数列，每个整数的绝对值不超过1000。 【输出格式】 一个整数，为最大的连续段和。 【输入样例】 5 1 -2 3 -2 3 【输出样例】 4,最大子段为3，-2,3,本题是需要从已经给的数据中找出一个连续的子段，使得其和最大。注意，不可以排序，必须在题目所给数据的基础上实现。,最大子段和问题解法多样，在这里只介绍三种。,解法(1)：,【算法概括】三重循环枚举实现,【算法分析】要在原数据中确定一个子段就需要知道这个子
2、段的“头”和“尾”，也就是这个子段的起始点和终点。我们可以使用两重循环来分别枚举“头”“尾”。因为要算最大子段和，所以还要用一重循环进行求和，一共就是三重循环。,【时间复杂度】O(n) 可以支持200以内的数据,模拟样例：,1 -2 3 -2 3,-1,2,0,3,1,模拟样例：,1 -2 3 -2 3,1 -1 2 0 3,-2,1,-1,2,模拟样例：,1 -2 3 -2 3,1 -1 2 0 3,-2 1 -1 2,3,1,4,模拟样例：,1 -2 3 -2 3,1 -1 2 0 3,-2 1 -1 2,3 1 4,-2,1,3,所以，最大的子段和为4,4,代码：,var n,i,j,k
3、,max,ans:longint; a:array1100of longint; begin read(n); for i:=1 to n do read(ai); ans:=-maxlongint; for i:=1 to n do for j:=i to n do begin max:=0;/注意初始化 for k:=i to j do max:=max+ak; if maxans then ans:=max; end; write(ans); end.,/不能不初始化或置为0,/不能像排序一样写，单个数字也可以作为子段,注释：,：答案初始化 Ans:=-maxlongint; 这里不可以
4、置为0或是不初始化。最大字段和求解的数据中一定会有负数的数据（如果都是正数最大子段和就是所有数字相加），所以置为0的错误的初始化，比如下面的这种数字就过不了。 5 -1 -2 -3 -4 -5 这个数据的最大子段和是-1（单个-1一段），但如果初始化为0或不初始化答案就会是0。,注释：,：枚举头尾 for i:=1 to n do for j:=i to n do/这里不能用像排序的循环方式： for i:=1 to n-1 do for j:=i+1 to n do 如果采用这样的循环方式所求的最大子段和就不包括单个数字为一段的答案。对于以下这种数据会出现错误。 5 1 -2 -3 -4 -
5、5 这个数据的最大子段和是1（单个1一段）。但如果采用错用的循环方式所做出的答案就会是-1（1和-2）。,解法(2)：,【算法概括】两重循环枚举+预处理,【算法分析】虽然第一种解法最容易理解，但是效率非常低，而且有很多的和是重复计算过的。比如计算第二个数到第五个数和第三个数到第五个数时，从第三个数到第五个数的和进行了重复计算。在这种情况下，可以进行一定的简单优化。用一重循环将第一个数到第i个数之间的和都先计算好，那么到枚举时就可以直接使用，省去了一重求和的循环。,【时间复杂度】O(n) 可以支持3000以内的数据,数据模拟：,用ti来表示从第1个数到第i个数的和,t1 t2 t3 t4 t5,
6、5 1 -2 3 -2 3,t,1,-1,2,0,3,则求第i个数到第j个数之间的和(ji)就是tj-ti-1,代码：,var n,i,j,k,ans:longint; a,t:array0100of longint; begin read(n); for i:=1 to n do read(ai); t1:=a1; for i:=2 to n do ti:=ti-1+ai;也可以写成for i:=1 to n do ti:=ti-1+ai;数组要从0开始定义 ans:=-maxlongint; for i:=1 to n do for j:=i to n do if tj-ti-1ans t
7、hen ans:=tj-ti-1; write(ans); end.,解法(3)：,【算法概括】动态规划求解,【算法分析】因为这一题是求连续的最大子段和， 阶段最优可以导致答案最优，当前最优不会影响后面的计算，所以可以很自然地想到动态规划。如果前i-1个数的最大子段和小于零那么从第一个数到第i个数的最大子段和就是ai，反之从第一个数到第i个数的最大子段和就是前i-1个数的最大字段和加ai。,【时间复杂度】O(n) 可以支持10000000以内的数据,数据模拟：,用fi来表示以ai结尾的最大子段和,f1 f2 f3 f4 f5,5 1 -2 3 -2 3,f,1,-1,3,1,4,代码：,var n,i,j,ans:longint; a,f:array0100of longint; begin read(n); for i:=1 to n do read(ai); ans:=-maxlongint; for i:=1 to n do begin if ai+fi-1ai then fi:=ai+fi-1 else fi:=ai; If fians then ans:=fi end; write(ans); end.,谢谢！,