下载文档原格式
最大子列和问题c语言最大子列和问题是计算机算法中的一个经典问题，也是一个比较基础的算法题目。
题目要求在一个给定的数组中，求出所有子数组中的最大值。
在解决这个问题时，我们可以使用暴力枚举法，它的时间复杂度为O(n^3)。
也可以使用分治法或动态规划的思想来解决，时间复杂度可优化至O(nlogn)或O(n)。
下面是一个使用C语言实现最大子列和问题的示例代码：```c#include <stdio.h>int maxSubArray(int* nums, int numsSize){int maxSum = nums[0];int sum = 0;for(int i=0; i<numsSize; i++){sum += nums[i];if(sum > maxSum){maxSum = sum;}if(sum < 0){sum = 0;}}return maxSum;}int main(){int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};int numsSize = sizeof(nums)/sizeof(nums[0]);int maxSum = maxSubArray(nums, numsSize);printf('The maximum subarray sum is %d', maxSum);return 0;}```在这个示例代码中，我们使用了一个变量sum来记录当前子数组的和，如果这个和大于当前最大值maxSum，就更新maxSum。
如果sum 小于0，说明当前子数组不能使总和更大，所以将sum重置为0。
以上就是一个使用C语言实现最大子列和问题的示例代码。
希望对大家学习算法有所帮助。
最大子数组和问题所谓最大子数组问题,就是在给定的一串包含正数,负数的数组中,找出最大的子数组的和例如:输入:1,-2,3,10,-4,7,2,-5最大子数组和为18一般而言,有三种办法可以用于解决这个问题1.暴力破解法暴力破解法就是将所有的子数组的和全部加起来，取最大的。
2.分治法分治法的核心思想就是将大问题分解为小问题,再将小问题逐个解决,然后从小问题的解得到原问题的解如果把数组从任一点(一般取中点)分为两个数组,那最大子数组只能存在于三个位置1.左数组2.右数组3.左数组最大后缀和右数组最大前缀的拼接(我称为中间数组)然后把分得的两个数组使用递归算法继续分割,直到每个子数组只含有一个元素此时两两进行判断:若左数组较大,并返回左数组的值,右数组一样若中间数组较大(此处即左右最大前缀和后缀的和,则返回这个和)3.动态规划法定义数组p,p[i]表示从arr[0]开始的前i项和,定义p[-1]=0,设arr=[1,-3,5,-2,4]则有:p[0]=max(p[-1]+arr[0],arr[0]) p[0]=max(0+1,1)=1;p[1]=max(p[ 0]+arr[1],arr[1]) p[1]=max(1-3,-3)=-2;p[2]=max(p[ 1]+arr[2],arr[2]) p[2]=max(-2+5,5)=5;p[3]=max(p[ 2]+arr[3],arr[3]) p[3]=max(5-2,-2)=3;p[4]=max(p[ 3]+arr[4],arr[4]) p[4]=max(3+4,4)=7;所以该数组的最大子数组之和为7不难发现p[i]的值是否改变的判断依据是p[i-1]+arr[i]是否大于arr[i]即p[i-1]+arr[i]>arr[i]?p[i]=p[i-1]+arr[i]:p[i]=arr[i];进一步思考,能否只用一个变量来起到代替数组p的作用呢?答案是肯定的经过观察,我们发现取到arr[i]这个值的前提是,arr[i]需要给我们的最大子数组之和的这个和带来正面作用,也就是让子数组之和更大,这样的话我们才会取到这个arr[i]所以,我们可以用一个变量thisMax表示当前累加的和,如果它加上arr[i]之后比原来的max更大(也就是对max起正面作用),那我们就把这一项算入到最大子数组当中,另外,如果thisMax+arr[i]之后导致arr[i]比原先还要小,我们就可以理解为thisMax在求最大子数组之和这件事上没有发挥正面作用,所以我们以arr[i]为第一项重新开始累计最大子数组之和.这样,只需要一个循环我们就可以解决问题。
最⼤字段和（四种⽅法）Description给定有n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列连续的⼦段和的最⼤值。
如果该⼦段的所有元素和是负整数时定义其最⼤⼦段和为0。
Input第⼀⾏有⼀个正整数n(n<1000)，后⾯跟n个整数,绝对值都⼩于10000。
直到⽂件结束。
Output输出它的最⼤⼦段和。
Sample Input6 -2 11 -4 13 -5 -2Sample Output201.暴⼒跑表法（时间复杂度（n³））（AC oj：912 ms）跑每⼀个点，⽤⼀个⼆维数组的坐标 i , j表⽰i -----> j 字段内的和。
分别求出后，跑这个⼆维数组，取出最⼤值。
1 #include <iostream>2 #include<string.h>3using namespace std;45int main()6 {7int n1;8int i,j,k,max1,m,n;9int sum=0;10 cin>>n1;11int ap[n1];12int a[n1][n1];1314for(i=0;i<n1;i++)15 cin>>ap[i];16 memset(a,0,sizeof(a)); //数组清零17 a[0][0]=ap[0];18for(i=0;i<n1;i++)19 a[i][i]=ap[i];20for(i=0;i<n1;i++)21for(j=i;j<n1;j++)22 {23if(i!=j)24 {25if(j!=0)26 {27 k=j-1;28 a[i][j]=a[i][k]+ap[j];29 }30 }31 }3233 max1=a[0][0];34for(i=0;i<n1;i++)35for(j=0;j<n1;j++)36 {37if(max1<a[i][j])38 {39 max1=a[i][j];40 m=i;41 n=j;42 }43 }44 cout<<max1;45return0;46 }2.暴⼒记忆法（时间复杂度（n²））（AC oj：12 ms）此⽅法同第⼀种⽅法，是暴⼒法的升级版。
【java】矩阵的最⼤⼦矩阵（动态规划）⼀、实验⽬的练习使⽤动态规划算法解决实际问题（使⽤Java语⾔实现）。
⼆、实验内容【问题描述】有⼀个包含正数和负数的⼆维数组。
⼀个⼦矩阵是指在该⼆维数组⾥，任意相邻的下标是1*1或更⼤的⼦数组。
⼀个⼦矩阵的和是指该⼦矩阵中所有元素的和。
本题中，把具有最⼤和的⼦矩阵称为最⼤⼦矩阵。
【⽰例】给出以下⼆维数组：0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2这个数组的最⼤⼦矩阵为：9 2-4 1-1 8其和为15。
【输⼊】输⼊包含多组测试数据。
每组输⼊的第⼀⾏是⼀个正整数N（1<=N<=100），表⽰⼆维⽅阵的⼤⼩。
接下来N⾏每⾏输⼊N个整数，表⽰数组元素，范围为[-127，127]。
【输出】输出最⼤⼦矩阵和。
【思路提⽰】求最⼤⼦矩阵和问题是求最⼤⼦段和问题在⼆维空间上的推⼴，可参考求最⼤⼦段和问题。
三、 程序代码（1）maxSumList1package maxSumList;2import java.util.Scanner;34public class maxList{5 //public static int[][] list=new int[10][10];6 static int n;7 private maxSingleList maxSingleList=new maxSingleList();8 private final maxSingleList[] maxSingleLists;9 private int numberOfmaxSingleLists;1011 public maxList() {12 //创建计算每个⼦段和的类的数组13 maxSingleLists=new maxSingleList[100];14 }15161617 public void InputList(int[][] list){1819 System.out.println("请输⼊⽅阵⼤⼩：");20 Scanner scanner=new Scanner(System.in);21 n=scanner.nextInt();22 for (int y=0;y<n;y++){23 System.out.println("请输⼊⽅阵第"+(y+1)+"⾏数据：");24 for (int x=0;x<n;x++)25 list[y][x]=scanner.nextInt();26 }27 }28 public void OutputMaxSumList(int[][] list){29 int m=0;30 int max=0;31 int max1=0;32 int maxnum=0;3334 for (m=0;m<=numberOfmaxSingleLists;m++) {35 max1=maxSingleLists[m].getSum();36 if (max1 > max) {37 max = max1;38 maxnum = m;39 }40 }41 System.out.println("请输出最⼤⼦段和："+maxSingleLists[maxnum].getSum());42 System.out.println("请输出最⼤⼦段：");43 for(int i=maxSingleLists[maxnum].getY1();i<=maxSingleLists[maxnum].getY2();i++){44 for (int j=maxSingleLists[maxnum].getNum1();j<=maxSingleLists[maxnum].getNum2();j++){45 System.out.print(list[i][j]+" ");46 }47 System.out.println("\n");48 }49 }5051 public void subMaxList(int[][] matrix) {52 int m=0;53 int[][] total = new int[10][10];54 for (int y=0;y<n;y++){55 for (int x=0;x<n;x++)56 total[y][x]=matrix[y][x];57 }585960 for (int i = 1; i < n; i++) {61 for (int j = 0; j < n; j++) {62 total[i][j] += total[i-1][j];63 }64 }6566 int maximum = 0;//Integer.MIN_VALUE;67 for (int i = 0; i < n; i++) {//所在的list⾏68 for (int j = i; j <n; j++) {//相差的69 //result 保存的是从 i ⾏到第 j ⾏所对应的矩阵上下值的和70 int[] result = new int[matrix[0].length];//每次都重新定义存放⼦段和的结果数组71 for (int f = 0; f < n; f++) {72 if (i == 0) {73 result[f] = total[j][f];74 } else {75 result[f] = total[j][f] - total[i - 1][f];76 }77 }78 maxSingleList maxSingleList=new maxSingleList();79 int maximal=maxSingleList.MaxListNum(result,i,j);80 numberOfmaxSingleLists=m;81 maxSingleLists[m++]= maxSingleList;81 maxSingleLists[m++]= maxSingleList;82 if (maximal > maximum) {83 maximum = maximal;84 }85 }86 }87 }8889}（2）maxSingleList4 private int num1;5 private int num2;6 private int y1;7 private int y2;8 private int sum;9 public int getNum1(){10 return num1;11 }12 public int getNum2(){13 return num2;14 }15 public void setY1(int y11){16 y1=y11;17 }18 public void setY2(int y22){19 y2=y22;20 }21 public int getY1(){22 return y1;23 }24 public int getY2(){25 return y2;26 }27 public void setSum(int sum){28 this.sum=sum;29 }30 public int getSum(){31 return sum;32 }33 public int MaxListNum(int[] array,int i,int j){34 int number,b=0,begin=0,bestmin=0,bestmax=0;35 sum=0;36 for (number = 0; number < array.length; number++) {//sum没清零37 if (b >= 0)//去掉等号38 b += array[number];39 else {40 b = array[number];41 begin = number;42 }43 if (b > sum) {//加个+44 sum = b;45 bestmin = begin;46 bestmax = number;47 }4849 }50 num1 = bestmin;51 num2= bestmax;52 setSum(sum);53 setY1(i);54 setY2(j);55 return sum;56 // if (sum==0)和为0的⾏数组要去掉那⼀⾏5758 }5960 }（3）TestmMaxList4 public static int[][] list=new int[10][10];5 public static void main(String[] arg){6 maxList maxlist=new maxList();7 maxlist.InputList(list);8 maxlist.subMaxList(list);9 maxlist.OutputMaxSumList(list); 1011 }12}四、 实验结果（含程序运⾏截图）五、 出现问题及解决⽅法（⼀）出现的问题在于算法的设计上，⼀开始我认为最⼤⼦矩阵就是每⾏所构成的最⼤⼦段的⾏列的序号交集，后来发现不是这样的，这样没办法正确输出最⼤⼦矩阵，得到的结果不对，然后推翻⾃⼰写了⼀天的代码以及想法。
动态规划——最⼤⼦段和⼀、最⼤⼦段和问题给定N个数A1, A2, ... An，从中选出k（k不固定）个连续的数字 Ai, Ai+1, ... Ai+k-1，使得∑i+k−1iAt 达到最⼤，求该最⼤值。
分析求最⼤⼦段和可以⽤多种算法来解决.（1）直接枚举max = 0;for i in [1...n]for j in [i....n]sum = 0;for k in [i...j]sum += A[k]if(sum > max)max = sum//时间复杂度为O(n^3)（2）求 sum[i...j]时，直接利⽤ sum[i...j] = sum[i...j-1] + A[j]来优化max = 0;for i in [1...n]sum = 0for j in [i....n]sum += A[j]if(sum > max)max = sum//时间复杂度为O(n^2)（3）分治法将A1...An⽤⼆分法分为左右两边，则A1...An中的最⼤连续⼦段和可能为三种情况：【1】是A1...An/2中的最⼤连续⼦段和【2】是An/2+1....An中的最⼤连续⼦段和【3】横跨左右两边int MaxSum(int* a, int beg, int end){if (beg == end){return a[beg] > 0? a[beg] :0;}int mid = (beg + end) / 2;int max_left = MaxSum(a, beg, mid);int max_right = MaxSum(a, mid + 1 ,end);int s1 = 0, s2 = 0, m_left = 0, m_right = 0;for(int i = mid; i <= beg; i --){s1 += a[i];if(s1 > m_left)m_left = s1;}for(int i = mid+1; i <= end; i ++){s2 += a[i];if(s2 > m_right)m_right = s2;}int max_sum = max_left;if(max_right > max_sum)max_sum = max_right;if(m_right + m_left > max_sum)max_sum = m_left + m_right;return max_sum;}//时间复杂度为 O(nlogn)（4）动态规划算法⽤动归数组 dp[i]表⽰以Ai结尾的若⼲个连续⼦段的和的最⼤值，则有递推公式：dp[i] = max{dp[i-1] + A[i], A[i]}int max = 0;for(int i = 1; i <= n; i ++){if(dp[i-1] > 0){dp[i] = dp[i-1] + A[i];}else{dp[i] = A[i];}if(dp[i]> max){max = dp[i];}}//时间复杂度为O(n)⼆、最⼤⼦矩阵和问题给定MxN的矩阵，其⼦矩阵R{x1, y1, x2, y2} (x1, y1) 为矩阵左上⾓的坐标，(x2, y2)为矩阵右下⾓的坐标，S(x1,y1,x2,y2)表⽰⼦矩阵R中的数字的和，求所有⼦矩阵的和的最⼤值。
动态规划：最⼤⼦矩阵 在DP问题中有⼀种叫最⼤⼦矩阵问题，刚好碰到了这⼀题，于是学习分享之。
让我们先来看⼀下题⽬：ZOJ Problem Set - 1074 题⽬分类：动态规划 题⽬⼤意：就是输⼊⼀个N*N的矩阵，找出在矩阵中，所有元素加起来之和最⼤的⼦矩阵。
例如在 0 -2 -7 0 这样⼀个4*4的矩阵中，元素之和最⼤的⼦矩阵为 9 2 ，它们之和为15。
9 2 -6 2 -4 1 -4 1 -4 1 -1 8 -1 8 0 -2 这是⼀个最⼤⼦矩阵问题，我们怎么来解决这个问题呢？任何问题都会有它的简化的问题，这是⼆维的数组，与之对应的，我们可以先尝试⼀下⼀维数组。
如果有⼀个⼀维数组a[n]，如何找出连续的⼀段，使其元素之和最⼤呢？ 例如有 1 2 -3 4 -2 5 -3 -1 7 4 -6 这样⼀个数组，那么显然 4 -2 5 -3 -1 7 4 这个⼦数组元素之和最⼤，为4+(-2)+5+(-3)+(-3)+7+4=14。
为找到⼀维数组的最⼤⼦数组，我们可以有以下⽅法。
1、穷举法1for(i=0;i<n;i++)2 {3for(j=0;j<=i;j++)4 {5 sum = 0;6for(k=j;k<=i;k++)7 sum += a[k];8if(sum > max) max = sum;9 }10 } 穷举法在n很⼤的情况下，需要运⾏的次数⾮常的多，有三层循环，所以n很⼤时不能使⽤这种⽅法。
2、带记忆的递推法1 record[0] = 0;2for(i=1;i<=n;i++) //⽤下标1~n来储存n个数3 record[i] = record[i-1] + a[i]; //⽤record记录a[i]前i个的和4 max = 0;5for(i=1;i<=n;i++)6 {7for(j=0;j<i;j++)8 {9 sum = record[i] - record[j];10if(sum > max) max = sum;11 }12 } 这种⽅法的时间复杂度明显⽐上⼀种的低了很多，时间复杂度为O(n²)。
子数组和的最大值我们需要明确一点，子数组的长度可以是任意的，可以包含一个元素，也可以包含整个数组。
因此，我们需要考虑到所有可能的情况。
那么，如何找到子数组和的最大值呢？一种常见的方法是使用动态规划。
我们可以定义一个dp数组，其中dp[i]表示以第i个元素结尾的子数组的最大和。
那么，我们可以得到如下的状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])其中，nums是给定的数组。
这个状态转移方程的意思是，以第i个元素结尾的子数组的最大和，要么是前面一个子数组的最大和加上当前元素，要么是当前元素本身。
接下来，我们需要遍历整个数组，计算出dp数组的值。
最终，dp 数组中的最大值就是子数组和的最大值。
除了动态规划，还有一种常用的方法是使用滑动窗口。
滑动窗口的思想是维护一个窗口，通过移动窗口的起始位置和结束位置来找到子数组和的最大值。
具体的步骤如下：1. 初始化窗口的起始位置和结束位置为0，子数组的和为0。
2. 当窗口的结束位置小于数组的长度时，执行以下操作：- 将窗口的结束位置向右移动一位，并将窗口内的元素加入子数组的和中。
- 如果子数组的和大于最大值，更新最大值。
- 如果子数组的和小于等于0，说明窗口内的元素对于子数组的和没有贡献，将窗口的起始位置向右移动一位，并将子数组的和重置为0。
3. 返回最大值作为子数组和的最大值。
这种滑动窗口的方法可以在O(n)的时间复杂度内找到子数组和的最大值，比动态规划更加高效。
除了上述两种方法，还有一些其他的方法可以解决子数组和的最大值问题。
例如，我们可以使用分治法，将问题划分为更小的子问题，然后再将子问题的解合并起来。
或者，我们可以使用前缀和的方法，先计算出每个位置的前缀和，然后通过计算两个前缀和的差值来得到子数组的和。
无论采用哪种方法，我们都可以在给定的数组中找到子数组和的最大值。
这个问题在实际生活中也有很多应用，例如在股票交易中，我们可以通过找到股票价格的最大涨幅来进行投资决策；或者在天气预测中，我们可以通过找到连续几天的最高温度和最低温度来预测未来几天的天气情况。
最⼤字段和问题最⼤⼦段和 -- 分治,dp1.问题描述输⼊⼀个整型数组，数组中的⼀个或连续多个整数组成⼀个⼦数组。
求所有⼦数组的和的最⼤值。
⽰例1:输⼊: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续⼦数组 [4,-1,2,1] 的和最⼤，为 6。
2.分析问题2.1 ⽅案1此题很显然可以⽤多层for循环解决, 时间复杂度为O(n^2) .2.2 ⽅案2, 图像压缩问题的变形采⽤dp的思路, 我们把这个数组分成不同的段, **dp[i] 表⽰以nums[i]结尾的那个段的最⼤字段和, 所以就存在nums[i]这个元素是加⼊前⼀段中, 还是⾃成⼀段这就是需要思考的问题, 如果dp[i-1] < 0, 如果nums[i]加⼊前⼀段中, 最⼤字段和为dp[i-1] + nums[i], 这个值必然⼩于nums[i], 因为dp[i-1]是负数, 负数加上⼀个数,必然⽐这个数⼩, 就像是⼀个数减了某个数, 肯定变⼩. 其他情况下只⽤求dp[i-1] + nums[i]和 nums[i] 的最⼤值即可 **通过上⾯的分析, 很容易写出状态转移⽅程// dp初始化dp[0] = nums[0]if(dp[i-1] < 0) dp[i] = nums[i]; // ⾃成⼀段if(dp[i-1] >= 0) dp[i] = Max(dp[i-1] + nums[i], nums[i])简化转移⽅程, dp[i-1]<0时, nums[i] + dp[i-1] 必然是⼩于nums[i]的, 其实也是在求Max(dp[i-1] + nums[i], nums[i]),所以这个题只⽤⼀个⽅程就搞定. 简化了if else的判断, 对程序性能提升也是有帮助的dp[0] = nums[0]dp[i] = Max(dp[i-1] + nums[i], nums[i])这个题很有个很坑的地⽅就是, dp中最后⼀个元素并不是最终要求的结果, 这个我们平时做的题有很⼤的出⼊, dp[i]的含义是以nums[i]结尾的那个段的最⼤字段和, 那么dp中最后⼀个元素表⽰的是以nums中最后⼀个元素结尾的那个段的最⼤字段和, 最⼤的字段和不⼀定以nums中最后⼀个元素结尾,所以要最终要求的⽬标是dp数组中的最⼤值public int maxSubArray(int[] nums) {if(nums == null || nums.length <= 0) throw new IllegalArgumentException();int[] dp = new int[nums.length];dp[0] = nums[0];for(int i = 1; i < nums.length; ++i){dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);}// return dp[nums.length-1]; 神坑int maxValue = Integer.MIN_VALUE;for(int j = 0; j < dp.length; ++j){if(dp[j] > maxValue)maxValue = dp[j];}return maxValue;3. ⽅案3采⽤分治的思路, 我们把数组从中间分开, 最⼤⼦序列的位置就存在以下三种情况最⼤⼦序列在左半边, 采⽤递归解决最⼤⼦序列在右半边, 采⽤递归解决最⼤⼦序列横跨左右半边, 左边的最⼤值加上右边的最⼤值时间复杂度分析T(n) = 2 F(n/2) + n时间复杂度O(nlgn)public int maxSubArray(int[] nums) {if(nums == null || nums.length <= 0) throw new IllegalArgumentException(); return helper(nums, 0, nums.length-1);}private int helper(int [] nums, int start, int end){if(nums == null || nums.length <= 0) throw new IllegalArgumentException(); if(start == end)return nums[start];int middle = start + (end - start) / 2;int leftSums = helper(nums,start, middle);int rightSums = helper(nums,middle+1, end);// 横跨左右两边int leftRightSums;// 左边的最⼤值int lsums = Integer.MIN_VALUE, temp = 0;for(int i = middle; i >= start; i--){temp += nums[i];if(temp > lsums)lsums = temp;}// 右边的最⼤值int rsums = Integer.MIN_VALUE;temp = 0;for(int j = middle+1; j <= end; j++){temp += nums[j];if(temp > rsums) rsums = temp;}leftRightSums = rsums + lsums;return Math.max(Math.max(leftSums, rightSums), leftRightSums);}。
昆明理工大学信息工程与自动化学院学生实验报告（ 2011 — 2012 学年 第 1 学期 ）课程名称：算法设计与分析 开课实验室：信自楼机房444 2012 年12月 14日一、上机目的及内容1.上机内容给定有n 个整数（可能有负整数）组成的序列（a 1,a 2,…,a n ），求改序列形如∑=jk ka1的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。
2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。
二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； 蛮力法设计原理：利用3个for 的嵌套（实现从第1个数开始计算子段长度为1，2，3…n 的子段和，同理计算出第2个数开始的长度为1，2，3…n-1的子段和，依次类推到第n 个数开始计算的长为1的子段和）和一个if （用来比较大小）,将其所有子段的和计算出来并将最大子段和赋值给summax1。
用了3个for 嵌套所以时间复杂性为○(n 3)；分治法设计原理：1）、划分：按照平衡子问题的原则，将序列（1a ，2a ，…，na ）划分成长度相同的两个字序列（1a ，…，⎣⎦2/n a ）和（⎣⎦12/+n a ，…，na ）。
2）、求解子问题：对于划分阶段的情况分别的两段可用递归求解，如果最大子段和在两端之间需要分别计算s1=⎣⎦⎣⎦)2/1(max2/n i an ik k≤≤∑=，s2=⎣⎦⎣⎦)2/(max12/n j n ajn k k≤≤∑+=，则s1+s2为最大子段和。
若然只在左边或右边，那就好办了，前者视s1为summax2,后者视s2 o summax2。
3）、合并：比较在划分阶段的3种情况下的最大子段和，取三者之中的较大者为原问题的解。
