最大子序列和问题求解

数据结构与算法

发布日期: 2016-03-17

本系列主要整理分享对一些数据结构和算法问题的总结和思考，供基础相对较差的人渐进地学习，也是自身复习和寻求提升的过程。(代码部分借鉴和取自数据结构和算法书籍)
本文主要分享对最大子序列求和问题的求解和思考。
欢迎讨论和吐槽。

问题描述

给定整数A1，A2…An(包含负数），求某一段(从第i个到第j个）的数字之和的最大值。
约定：所有整数均为负数，最大值为0(降低复杂度)
例： 1，-3,3，-2，5，-6，其中最大值是3 到5 ，和为6.
问题分析

例子中的数字较少，我们可以直观的观察就得出结论，这其实是变相的穷举法。
根据问题的分析，我们可以得到下面两个结论
- 若前面的和为最大值，下一个数或者接下来n个数为整数，则接下来几个数应该被算进去；
- 若两段的和都为正数，无法合在一起，取和较大的一串。
  求解思路
  这里分享3个解决的思路和算法实现(代码为C)。

穷举和，找到最大的结果。

int max(int data[], int length) {
int sum,maxSum,i,j;
maxSum = 0;
for(i=0;imaxSum) {
   maxSum = sum;
 }
}
}
return maxSum;
}

接来下的方法很好的使用了递归这个武器，上面的方法1比较直观，很容易想到，但是穷举法的效率一般是不高的，我们
可以使用分治策略，把问题化小去解决。
针对这个问题最核心的思路是这样的：
- 这个序列分为两部分，分别求出左半部分的最大和，右半边的最大和，还有一种可能是结果在两部分中，因为序列是连续的，这种情况下必然包含左边的最后一个元素和右边的第一个元素，然后我们以这两点为起点一直计算下可以得到这种情况下的最大值，将三个最大值进行比较得到最大值即为最后的结果。
- 分出的两部分也递归的用上面的思想求出最大值。
```
int max(int data[],int left,int right) {
int maxLeftSum,maxRightSum;
int maxLeftPart,maxRightPart,leftPartSum,rightPartSum,center,i;
if(left==right) {              //分到最小结果的返回
if(data[left]>0) {
 return data[left];
} else {
 return 0;
}
}
center = (left+right)/2;
maxLeftSum = max(data,left,center);  //左半部分的最大和
maxRightSum = max(data,center+1,right); //右半部分的最大和
maxLeftPart = 0;
leftPartSum = 0;
for(i = center;i>=left;i++) {
leftPartSum += data[i];
if(leftPartSum>maxLeftPart) {
maxLeftPart = leftPartSum;
}
}
maxRightPart = 0;
rightPartSum = 0;
for(i = center+1;i<=left;i++) {
rightPartSum += data[i];
if(rightPartSum>maxRightPart) {
  maxRightPart = rightPartSum;
}
}
maxCenterSum = maxRightPart+maxLeftPart;
return  ;       //返回三个最大值中的最大值
}
```
  3.这个方法是针对本题目的一种灵活的解法：
- 我们每新加一个数，若和增大，则更新最大和；
- 若最大和大于0，则继续基于此最大和进行判断，若小于0，则对于后面的序列而言前面应该舍弃，此时从下个元素开始从新开始查找结果与前面的最大和进行比较；
- 这个方案的思路简单来说是从第一个元素，然后每次增加一个元素，判断增加前的最大和，与增加后的和比较，然后得出最大值
```
int max(int data[],int length) {
int sum,maxSum,i;
sum = maxSum = 0;
for(i=0; imaxSum) {
 maxSum = sum;
} else if(sum<0) {
 sum = 0;               //从下一个元素开始重新计算
}
}
}
```