题目描述：连续子数组的最大和（连续最大公共子序列） 或许其实只有4个解法（看最后总结）
思路1：复杂度最高也是最直观的，求得所有的子序列，进行比较。时间复杂度O(n^3)
思路2：对第一个算法进行改进。有些重复计算的值，避免再次计算，因此时间复杂度O(n^2)
思路3：使用分治的思想，同时也使用了递归。时间复杂度O(n*logn)
思路4：动态规划，时间复杂度O(n)
思路5：叫不出名字的解法，有的称扫描法？而且时间复杂度也仅为O(n)
思路1实现代码：
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int maxSum = array[0];//如果设为0，在某些负数数组中会出错
int sum;
//最外层循环，每一层循环，都能拿到以当前角标i为数组的第一个元素时，所有子序列的最大值
//如{1，-1，4，8}就分成{1，-1，4，8} {-1，4，8} {4，8} {8}四个部分分别求
for (int i = 0; i < array.length; i++) {
//第二层循环，以i=1为例，{-1，4，8} 由于j的递增，又分成了{-1，4，8}{4，8}{8} 三组
for (int j = i; j < array.length; j++) {
sum = 0;
//第三次循环，以i=1为例，j=1时，k的变化得到{-1} 结果 -1
//第三次循环，以i=1为例，j=2时，k的变化得到{-1，4} 结果3 -1+4
//第三次循环，以i=1为例，j=3时，k的变化得到{-1，4，8} 结果11 利用循环求和-1+4+8
for (int k = i; k <= j; k++) {
sum += array[k];// 计算a[i]到a[j]的和
}
if (sum > maxSum) {
maxSum = sum;
}
}
}
return maxSum;
}
}思路2实现：可以看到，{1，-1，4，8}在第以i=1为例，j=3时，第三轮得到{-1，4，8}的和的过程是通过一轮循环 -1+4+8得到，但是k变化的这一轮循环是完全可以避免的，可以用{-1，4}的结果加上8这样的方式得到。因为{-1，4}在j=2的时候已经计算过了，不需要再次循环从-1+4+8来一次循环，而是用之前计过的算结果就好了，因此可以降低复杂度，代码实现如下
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int maxSum = array[0];
int sum;
//最外层循环,如{1，-1，4，8}就分成{1，-1，4，8} {-1，4，8} {4，8} {8}四个部分分别求
for (int i = 0; i < array.length; i++) {
sum = 0;
//以i=1为例 {-1，4，8} 在完成整个第二轮循环中，计算的结果是-1,3(-1+4),11(3+8)
//第二种方法计算11的过程是没有用循环的，而是用上一个的结果3加8得到本次结果。
//第一种方法得到11是-1+4+8，需要循环计算
for (int j = i; j < array.length; j++) {
sum += array[j];
if (sum > maxSum) {
maxSum = sum;
}
}
}
return maxSum;
}
}思路3：分治--把问题分成两个大致相等的子问题，然后递归地对它们求解，这是“分”的部分。“治”阶段将两个子问题的解修补到一起，并可能再做些少量的附加工作，最后得到整个问题的解。
将数组分成两半后，问题的结果可能出现在左边，可能在右边，还可能左边有一部分元素，右边也有一点元素。
例如：D通过递归调用左B和右C,B告诉左最小，c告诉右最小，那么D本身还需要补一个跨中间的比较，然后三个值比较后return，返回的是D整体的最大值。在B中，通过递归调用E,F时，也会运行一个跨中间的比较，然后三值比较，进行return（那么D获得B整个部分的最大），在C通过递归调用G，H时，也会运行一个跨中间的比较，然后三值比较，进行return（那么D获得了C整个部分的最大）
本份代码调整了maxLeftBorderSum和maxRightBorderSum的赋初值的情况，可以进行所有元素是负数的情形，网上看了很多示例，都不能解决所有元素是负数的情况。另外边界条件也是分治（递归）值得注意的。
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
return way(array,0,array.length-1);
}
public static int way(int [] arr,int left,int right) {
//这是递归的返回情况，左右边界相等，直接返回
if (left == right) {
return arr[left];
}
//分割序列 分成两半
int center = (left + right) / 2;
//递归处理子序列 注意，递归返回的是子序列的最大值
int maxLeftSum = way(arr, left, center);
int maxRightSum = way(arr, center+1, right);
//处理左序列 从中间边界向左边界计算
//上面两行拿到了左和右两个部分最大值，现在处理合起来的部分
int maxLeftBorderSum = arr[center]; //左边界中，求和过程中的，带着center点的最大值
int leftBorderSum = 0; //左边界求和的值
//通过本轮循环，可以达到当前左边部分的最大值
for (int i = center; i >= left; i--) {
leftBorderSum += arr[i];
if (leftBorderSum > maxLeftBorderSum) {
maxLeftBorderSum = leftBorderSum;
}
}
//处理右序列 从中间边界向后边界计算
int maxRightBorderSum = arr[center+1];//右边界中，带着center+1点的最大值
int rightBorderSum = 0; //这是右边界所有的和
for (int i = center+1; i <= right; i++) {
rightBorderSum += arr[i];
if (rightBorderSum > maxRightBorderSum) {
maxRightBorderSum = rightBorderSum;
}
}
//返回最大子序列和 maxLeftBorderSum+maxRightBorderSum是包含center中点的情况
//所以是三个数，包含中间，左最大，右最大
return Max(maxLeftBorderSum+maxRightBorderSum,maxLeftSum,maxRightSum);
}
//三元运算求最值
public static int Max(int a,int b, int c) {
return a > b? (a > c ? a : c ): (b > c ? b : c);
}
}第四种 动态规划（摘过来的答案，以后再来理解）
1、状态方程 ： max(dp[i]) = getMax(max(dp[i-1]) + arr[i] ,arr[i])
2、上面式子的意义是：我们从头开始遍历数组，遍历到数组元素 arr[i] 时，连续的最大的和可能为
max(dp[i-1])+arr[i]，也可能为arr[i] ，做比较即可得出哪个更大，取最大值。时间复杂度为O(n)。
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length == 0) return 0;
int sum = array[0];
int temp = array[0]; //注意初始值 不能设为0 防止只有负数
for(int i = 1; i < array.length; i++) //从1开始 因为0的情况在初始化时完成了
{
temp = (temp < 0) ? array[i] : temp + array[i];
sum = (temp > sum) ? temp : sum;
}
return sum;
}
}思路5：
我们可以从第一个数开始算起,每往后加一个数便更新一次和的最大值;当和成为负数时,则表明此前序列无法为后面提供最大子序列和,（不管后面是否正负，你这里为负数，加上你这个负数就更小了，还不如不加）因此必须重新确定序列首项，虽然重新确定序列首部，但是我已经用一个变量记录了之前的最大值了。
极端情况：全是负数时，temp变量一直是等于某个单个的元素，在移动，并与max比较，因此max通过比较也等于的是最小的负数
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int maxSum = array[0]; //设置为0，会导致有全负的数组的结果为0的错误
int temp = 0;
for( int i = 0; i < array.length ; i ++ ){
temp += array[ i ];
if(temp > maxSum)
maxSum = temp;
else if(temp < 0)
temp = 0;
}
return maxSum;
}
}发现上下这两种解法其实是一个意思
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int temp=array[0];
int maxSum=array[0];
for(int i=1;i<array.length;i++){
if(temp<0)
temp=array[i];
else
temp+=array[i];
if(temp>maxSum)
maxSum=temp;
}
return maxSum;
}
}
总结，虽然动态规划的原理我现在暂时不懂，但是从代码上看，貌似摘过来的动态规划代码所描述的过程，和第五种思路的两种解法都非常相似。
无非就是（临时求和变量temp ）temp小于0时，则temp应该重新赋值，而上面的写法有些是赋值0，有些是等于下个变量，其实是一个意思，因为你下一步总是要加下一个变量A，即temp=A,或者是temp=0再temp+=A，这两个写法上面都有，没区别。而如果temp大于0，就让temp加上下一个变量A，也就是temp=temp+A。再判断temp和当前记录的最大值maxsum，更新最大值。然后进入下一轮判断。三份代码的流程都是这样的，可能思路不同，但是写出代码的执行过程却非常相似，菜鸟表示很疑惑。
总之：由于复杂度是O(n)，意味着每个元素只扫描了一次，需要保证扫描一次后，当前保留的maxsum是扫描过的最大值，所以意味着，最大子序列的头部在移动，并不是一直保持索引为0。所以扫描过程中需要跳过一些负面元素的影响，而temp就起到了这个所用。
京公网安备 11010502036488号