楼主这篇文章的目的是要带大家梳理一下，有关于求子数组问题。如求子数组的最大和，求最大和的子数组，求最大积的子数组等一系列问题。今天阳光明媚，楼主今天心情很好哦，愿大家开心每一天，哈哈。Are you ready?开始了哦~~~
题目一：求子数组的最大和
题目求子数组的最大和，这里需要注意的一个问题就是，子数组那么便意味着是连续的一段数据。我们可以先写的例子，方便我们注意到要考虑的一些问题。
数组：[1, -2, 3, 5, -3, 2] 应该返回8，最大和的子数组为3，5 数组：[0, -2, 3, 5, -1, 2] 应该返回9，最大和的子数组为3, 5，-1，2 数组：[-1, -2, -3, -4, -5]应该返回-1，最大和的子数组为-1 这里，我们只介绍一种时间复杂度为的算法来求解。
解法一：分治法
将所给数组，分别求出这两段数组各自的最大子段和，则原数组的子数组的最大和可以分为下面三种情况：
看下面代码：
#include <iostream> #include <limits>using namespace std; int getMAX3(int a, int b, int c);int getBiggestSubSum(int *pArray, int low, int high);int main() {int a1[] = {1, -2, 3, 5, -3, 2};int a2[] = {1, -2, 3, 5, -1, 2};int a3[] = {-1, -2, -3, -5, -3, -2};cout << “数组1的子数子的最大和为” << getBiggestSubSum(a1, 0, sizeof(a1) / sizeof(int) – 1) << endl;cout << “数组2的子数子的最大和为” << getBiggestSubSum(a2, 0, sizeof(a2) / sizeof(int) – 1) << endl;cout << “数组3的子数子的最大和为” << getBiggestSubSum(a3, 0, sizeof(a3) / sizeof(int) – 1) << endl;system(“pause”);} int getBiggestSubSum(int *pArray, int low, int high){int middle = (low + high) >> 1; //获取中间节点的下标int MAX = numeric_limits<int>::min();if (high == low){//递归到只剩下一个数之后，那么直接返回return pArray[low];}int lMax = numeric_limits<int>::min();int rMax = numeric_limits<int>::min();int mMax = numeric_limits<int>::min();int mMaxTemp = 0;//求左半部分的最大和lMax = getBiggestSubSum(pArray, low, middle);//求右半部分的最大和rMax = getBiggestSubSum(pArray, middle + 1, high);//求横跨中间的最大和for (int i = middle; i <= high; i++){mMaxTemp += pArray[i];mMax = max(mMax, mMaxTemp);}for (int i = middle – 1; i >= 0; i–){mMaxTemp += pArray[i];mMax = max(mMax, mMaxTemp);}//返回三大部分最大和之间的最大值return getMAX3(rMax, mMax, lMax);}int getMAX3(int a, int b, int c){int max = a;max = (b > max) ? (b):(max);max = (c > max) ? (c):(max);return max;}
算法复杂度：。
解法二：动态规划法
我们可以考虑数组的第一个元素跟$A[0]的关系，有以下几种情况：
从上面三种情况可以看出来，我们可以将一个大问题，转化成一个较小的问题。如本题中，我们可以将一个N维数组的子数组最大和问题，转化成N-1维的子数组最大和问题。假设已经知道。那么根据上面的分析可知
上述公式中，第一项表示只有一个无关。看下面代码：
; int getBiggestSubSum(int *pArray, int len);int main() {int a1[] = {1, -2, 3, 5, -3, 2};int a2[] = {1, -2, 3, 5, -1, 2};int a3[] = {-1, -2, -3, -5, -3, -2};cout << “数组1的子数子的最大和为” << getBiggestSubSum(a1, sizeof(a1) / sizeof(int)) << endl;cout << “数组2的子数子的最大和为” << getBiggestSubSum(a2, sizeof(a2) / sizeof(int)) << endl;cout << “数组3的子数子的最大和为” << getBiggestSubSum(a3, sizeof(a3) / sizeof(int)) << endl;system(“pause”);} int getBiggestSubSum(int *pArray, int len){//从数组的最后一个元素开始,当只有一个元素的时候，那么start和all当然都是等于这个数啦int nStart = pArray[len – 1];int nAll = pArray[len – 1];for (int i = len – 2; i >= 0; i–){nStart = max(pArray[i], nStart + pArray[i]);nAll = max(nAll, nStart);}return nAll;}
运行结果：
数组1的子数子的最大和为8数组2的子数子的最大和为9数组3的子数子的最大和为-1请按任意键继续. . .
算法复杂度：
题目二：求子数组的最大和并输出相应的子数组我们人生中最大的懒惰，就是当我们明知自己拥有作出选择的能力，
