最大子段和问题-精选.ppt

数据模拟： 用t[i]来表示从第1个数到第i个数的和 t[1] t[2] t[3] t[4] t[5] 5 1 -2 3 -2 3 t 1 -1 2 0 3 则求第i个数到第j个数之间的和(ji)就是t[j]-t[i-1] * 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 大吉大利 最大子段和问题 制作：七(10)班王晶晶 * 【题目描述】 给定一组数列，求连续子段和最大值。 【输入格式】 第一行一个数n，表示数列长度（n=100000） 第二行，n个数，表示一个数列，每个整数的绝对值不超过1000。 【输出格式】 一个整数，为最大的连续段和。 【输入样例】 5 1 -2 3 -2 3 【输出样例】 4 最大子段为3，-2,3 * 本题是需要从已经给的数据中找出一个连续的子段，使得其和最大。注意，不可以排序，必须在题目所给数据的基础上实现。 最大子段和问题解法多样，在这里只介绍三种。 * 解法(1)： 【算法概括】三重循环枚举实现 【算法分析】要在原数据中确定一个子段就需要知道这个子段的“头”和“尾”，也就是这个子段的起始点和终点。我们可以使用两重循环来分别枚举“头”“尾”。因为要算最大子段和，所以还要用一重循环进行求和，一共就是三重循环。 【时间复杂度】O(n3) 可以支持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,max,ans:longint; a:array[1..100]of longint; begin read(n); for i:=1 to n do read(a[i]); 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+a[k]; if maxans then ans:=max; end; write(ans); end. ①//不能不初始化或置为0 ②//不能像排序一样写，单个数字也可以作为子段 * 注释①： ①：答案初始化 Ans:=-maxlongint; 这里不可以置为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 这个数据的最大子段和是1（单个1一段）。但如果采用错用的循环方式所做出的答案就会是-1（1和-2）。 * 解法(2)： 【算法概括】两重循