题目描述

给定一段长度为n的序列，我们需要找到其中一个连续的子段，使这个子段中各个元素加和最大，如果这个数组中全为负整数，我们就定义这个子段和为0.

题目分析

首先我们的目的是找一个局部的子段但加和是全局最大，所以我们可以很自然地想到，直接暴力法遍历求解即可。
方法一.暴力法求解
我们设置一个i，从第1个位置开始遍历，这个i表示的是我们最大子段的起始位置，然后我们从j=i往后接着遍历，j表示的是我们最大子段的末尾位置。接着从初始位置到末尾位置的元素累加求和，不断更新最大值即可。
暴力法代码

#include <iostream>
using namespace std;
int Maxsum(int n,int *a,int &besti,int &bestj)
{int sum = 0;for(int i = 1;i <= n;i++)//个人编程习惯，数组第一个位置从1开始{for(int j = i;j <= n;j++){int thissum = 0;//当前最大值，我们用它来更新sumfor(int k = i;j <= j;k++){thissum += a[k];}if(thissum > sum){sum = thissum;besti = i;//最优区间的开头bestj = j;//最优区间的结尾}}}return sum;
}

暴力法通常都可以解决问题，但也绝不是最好的方法，它的时间复杂度是极大的。大家可以看到，我们的代码中用了三层嵌套循环，所以这个方法的时间复杂度是O(n^3)，空间复杂度是O(1)
方法二.暴力法的改良
暴力法的时间复杂度过高，我们可以基于传统的暴力法再优化一点。就是在我们移动末尾区间的时候，边移动边求和。不用等到末尾区间固定了之后再遍历求和。
暴力法改良代码

#include <iostream>
using namespace std;
int Maxsum(int n,int *a,int &besti,int &bestj)
{int sum = 0;for(int i = 1;i <= n;i++)//个人编程习惯，数组第一个位置从1开始{int thissum = 0;for(int j = i;j <= n;j++){thissum += a[j];if(thissum > sum){sum = thissum;besti = i;//最优区间的开头bestj = j;//最优区间的结尾}}}return sum;
}
我们减少了一层循环，所以时间复杂度减少为了O(n^2),空间复杂度为O(1)

方法三.分治法
分治法是解决数组问题很常用的一种方法，我们对分治法情有独钟又敬而远之。其实分治法的本质就是递归，只要想着，我 们就负责把问题给你分开，分开的问题就留给你计算机自己处理。
分治法解题有三种情况:
1,这个最大子段在我们数组的左侧
2.这个最大子段在我们数组的右侧
3.这个最大子段跨过了左右两侧，在中间最大。
下面我们会分别讨论这三种情况。
第一种和第二种我们很简单，我们只需要简单地递归来解题，将两个子问题递归解出。分开的位置就是我们的中心位置。
第三种情况，我们假设跨过中心的子段在左侧的最大值为s1,在右侧的最大值为s2.则这个完整子段的最大值就是s1+s2。看吧，我们又把问题分成了两个。分别求解就好了。
分治法代码

#include <iostream>
using namespace std;
int Maxsubsum(int *a,int left,int right)
{int sum = 0;if(left == right)return a[left] > a[right] ? a[left] : a[right];else{int center = (left + right) / 2;int leftsum = Maxsubsum(a,left,center);int rightsum = Maxsubsum(a,center+1,right);int s1 = 0;int lefts = 0;//从中心向左侧遍历求最大for(int i = center;i >= left;i--){lefts += a[i];if(lefts>s1)s1 = lefts;//为了防止我们加入了负数，所以每次都应该执行这部操作来判断}//对于右侧同理int s2 = 0;int rights = 0;//从中心向右侧遍历求最大for(int j = center+1;j <= right;j++){rights += a[j];if(rights > s2)s2 = rights;}sum = s1 + s2;if(sum < leftsum)sum = leftsum;if(sum < rightsum)sum = rightsum;}return sum;
}
//但是这个方法我们也可以找到最优的区别，只需要稍微修改下上面的程序
int Maxsum(int n,int *a)
{return Maxsubsum(a,1,n);
}

数组被我们不断二分，分的次数为k,所以n = 2^k,遍历的时间复杂度为n，所以这个方法的时间复杂度为O（nlogn）
动态规划法
接下来就是最核心的方法了，其实这道题相信很多朋友看到了第一时间就会想到动态规划法，没错，这确实也是最简单的方法。

我们先开辟一个新的数组b,b[k]存储的是遍历到a[k]时的最大子段和。我们假设现在访问到了第j个位置，则a[j]位置的最大子段和应该是b[j]，所以我们应该更新b[j]=b[j-1]+a[j]
但是如果b[j-1]<0的话，我们就不做上述更新了，因为a[j]+b[j-1]一定小于a[j]，所以我们就让b[j]=a[j]即可。
动态规划法代码

#include <iostream>
using namespace std;
int Maxsum(int n,int *a)
{int sum = 0,b = 0;for(int i = 1;i <= n;i++){if(b > 0)b += a[i];elseb = a[i];if(b > sum)sum = b;}return sum;
}

动态规划法我们只遍历了一次数组，所以时间复杂度为O(n).

总结

对于数组问题，无论是一维或者二维，求最大或最小值一定会涉及到一个回溯或者动态规划问题，我们需要回头找到一个最值，或者直接干脆将前面的最值存起来。从而可以简化我们的计算。但是有的时候单纯运用动态规划法反而会造成更大的时间浪费，所以可能还需要一些小小的优化。具体例子可见我的另一篇博客：最长单调递增子序列