关键词：
前言
最近工作不是特别忙，所以有更多时间来学习算法相关知识，补短处。题目来源于leetcode，通过一个算法题，我们去分析该算法题所属类型，以及解题思路，以及该算法题所用到的数学知识。选择的算法题目从容易到困难，逐步提高难度，解题的思路也是从简单到复杂，时间复杂度也是从低到高的顺序来书写这个系列的博客。因工作语言和使用熟练度原因算法采用Java编写，但该系列中可能会穿插c、C++、python语言实现，请不要奇怪。
题目
分析题目：给定的整型数组，求解最大连续子数组和，要求是至少包含一个元素，且算法时间复杂度至少O(n).
首先我们想到就是：计算所有子数组的和进行比较取最大值，该方式叫做暴力求解，如果在数据规模很小的情况下我们就可以很轻松的接触结果，但一旦 规模稍微大一些，其性能就及其低了。那么我们先来写一下暴力求解算法实现。
暴力求解算法
// 1.暴力解析
private static int maxSubArrayByVoilence(int[] nums)
if(nums.length == 1)
return nums[0];
int currentSubSum,maxSubSum=nums[0];
// 思路: 1.暴力破解。遍历子数组的和进行比较
for(int i =0; i < nums.length; i++)
for (int j = i; j < nums.length; j++)
// 当前子数组和
currentSubSum = 0;
for (int k = i; k <= j; k++)
currentSubSum += nums[k];
// 比较最大值与当前子数组和
if(currentSubSum>maxSubSum)
maxSubSum = currentSubSum;
return maxSubSum;
分析：该解题方法的时间复杂度为O(n^3).效率非常低，但逻辑非常简单。针对暴力破解算法，我们可以考虑进行优化，使其时间复杂度降低为O(n^2),因为简单所以不再这里多写，同时也留给读者自行编写，如果可以你可以留言下来给其他读者或者给我看，看看你的优化思路。
最大连续子数组问题让我想到了《数据结构与算法》中的一个名词：最优解问题。该类问题就是属于最优解类型的题目，所以我们可以通过最优解问题的解题思路来解决这个算法题目：动态规划算法。
动态规划算法
动态规划算法-百度词条
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
上面是百度词条的解释，理解起来不难，那么我们这个问题，该如何实现算法呢？废话不多说，代码先撸出来。
// 3.动态规划
private static int maxSubArrayByDP(int[] nums)
if(nums.length == 1)
return nums[0];
int maxSubSum = nums[0],currentSubSum = nums[0];
for(int i=1;i<nums.length;i++)
currentSubSum += nums[i];
// 如果加上nums[i]后反而更小了，则从nums[i]开始重新计算
if(currentSubSum < nums[i])
currentSubSum = nums[i];
// 比较大小
if(currentSubSum > maxSubSum)
maxSubSum = currentSubSum;
return maxSubSum;
分析：动态规划算法时间复杂度为O(n),相比较于暴力解法效率就大大提升了。关键点在于如果加上nums[i]后相比较nums[i]小，那么说明i之前和比i数值小，所以既然比之前小，那么就可以把前面的都抛开重新规划计算和。
动态规划的数学表达：currentSubSum(i)表示数组下标以i为起点的最大连续下标最大的和，而maxsum(i)表示前i个元素的最大子数组之和。那么我们就可以推出下一个maxsum(i+1)应该为cursum(i+1)和maxsum(i)中选取一个最大值。递推式为：
currentSubSum(i) = maxA[i],currentSubSum(i-1)+A[i];
maxSubSum(i) = maxmaxsum(i-1),currentSubSum(i+1);
根据follow up的说明，还可以使用分治法去求解这个算法题。那么我们接下来看看分治法如何实现这个算法。
分治算法
// 4.分治算法+递归
private static int maxSubArrayByDC(int[] num, int low, int high) throws Exception
// 终止条件
if(low==high)
return num[low];
else if(low<high)
int mid = (low+high)/2;
// 左侧最大子数组和计算
int left = maxSubArrayByDC(num,low,mid);
// 右侧最大子数组和计算
int right = maxSubArrayByDC(num,mid+1,high);
// 跨越分区子数组和计算
int sum=0,max=0,i=0,j=0,center=0;
for(i=mid;i>=low;i--)
sum+=num[i];
if(sum>max)
max = sum;
center+=max;
max = -1;
sum=0;
for(j=mid+1;j<=high;j++)
sum+=num[j];
if(sum>max)
max = sum;
center+=max;
j = left>=right?left:right;
j = j>=center?j:center;
return j;
else
// 抛出异常
throw new Exception("索引值错误，low值一定不能比high值大");
分析:分治法处理规模大的问题时，采用的是缩小规模，然后比较各个规模的结果，从而得出最终结果。分治法的时间复杂度为O(nlogn)这里关键是理解分治思想，对于分治思想，我从网上找了一张图片，如下，能够很好的帮助我们理解和记住这种思维方式。
总结
该算法题虽然是很简单的一道题目，但包含的算法思想非常优秀。该系列的文章，我会陆续的写一些题目的解法，但不会所有LeetCode题目都写，我选择题目的要求是：有意思（包括多种有意思的解题算法，或者我不懂的算法）的，有技巧的，有深度的。如果你对这题有更多想说的可以在下面留言和读者讨论，我也会一起参与的哟。
连续子数组的最大和问题(代码片段)
...中找出一个连续子数组，要求该连续子数组中各元素的和最大，这个连续子数组便被称作最大连续子数组。比如数组2,4,-7,5,2,-1,2,-4,3的最大连续子数组为5,2,-1,2，最大连续子数组的和为5+2-1+2=8。问题输入就是一个数组，输出该数... 查看详情
动态规划求解连续子数组最大和问题（应该是新的描述方法？）
...提出如下解决方案：首先再重复下动态规划的定义：将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。 思考状态转移方程：设d[i]表示i个数形成的... 查看详情
最大连续子矩阵和算法(代码片段)
最大连续子矩阵算法暴力求解不可取或许可以从O(n)复杂度内求解最大连续子数组的算法得到灵感O(n2)复杂度求最大连续子矩阵和算法：创建一个新矩阵sum，sum[i][j]存放sun[i][0-j]的和每个候选矩阵由左上角matrix[i][j]和右下角的元素m... 查看详情
数组---最大子序列和(代码片段)
...经实现复杂度为O(n)的解法，尝试使用更为精妙的分治法求解。暴力法：1classSolution2public:3in 查看详情
转-求解最大连续子数组的算法
#include"stdafx.h"//暴力法求最大子数组和问题int_tmain(intargc,_TCHAR*argv[])intA[8]=-6,10,-5,-3,-7,-1,-1;intarray_length=sizeof(A)/sizeof(A[0]);//数组大小intsum=-10000;//记录子数组的和intlow;//记录子数组的底intheight;//记录子数组的高f 查看详情
hdu1003maxsum最大连续子序列之和(代码片段)
...终点。解题思路：最长连续子序列之和问题其实有很多种求解方式，这里是用时间复杂度为O(n）的动态规划来求解。思路很清晰，用dp数组来表示前i项的最大连续子序列之和，如果dp[i-1]>=0的话，则dp[i]加上dp[i-1]能够使 查看详情
30.连续子数组的最大和(代码片段)
...了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:6,-3,-2,7,-15,1,2,2,连续子向量的最大和... 查看详情
53.最大子序和(代码片段)
...经实现复杂度为O(n)的解法，尝试使用更为精妙的分治法求解。 O(n)复杂度：classSolut 查看详情
最大子阵列／连续数组的最大和(代码片段)
问题描述在一个数组中找出和最大的连续几个数（至少包含一个数)。例如：数组A[]=[?2,1,?3,4,?1,2,1,?5,4]，则连续的子序列[4,?1,2,1]有最大的和6。输入格式第一行输入一个不超过1000的整数n。第二行输入n个整数A[i]。输出格式第一行... 查看详情
剑指offer-连续子数组的最大和(代码片段)
题目：连续子数组的最大和题目描述：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决... 查看详情
1.(53)最大子序和(代码片段)
...经实现复杂度为O(n)的解法，尝试使用更为精妙的分治法求解。方法1:分治法分治法解决问题的模板:定义基本情况将问题分解为子问题并递归地解决他们合并子问题的解以获得原问题的解算法当最大子数组有n个数字:如果n==1,返回... 查看详情
动态规划_连续子数组的最大和(代码片段)
...了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:6,-3,-2,7,-15,1,2,2,连续子向量的最大和... 查看详情
剑指offer连续子数组的最大和(代码片段)
...了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:6,-3,-2,7,-15,1,2,2,连续子向量的最大和... 查看详情
剑指offer连续子数组的最大和(代码片段)
...了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:6,-3,-2,7,-15,1,2,2,连续子向量的最大和... 查看详情
算法导论最大子数组(代码片段)
...称这样的连续子数组为最大子数组。 2.用分治策略来求解。 a.假设我们要求A的子数组A[low,high]的最大子数组。根据分治策略，我们先将A[low,high]平分 b.那么A[low,highj]的子数组A[i,j]只有三种可能 a）完全位于A[low,... 查看详情
最大连续子数组和算法(代码片段)
求最大连续子数组和问题sampleinput:-1,4,-3,6,-20,4,-2,5sampleoutput:7最容易想到的就是暴力解决方法，穷举所有连续子数组的可能性，进行比较，复杂度O(n2)代码略复杂度为O(n)的算法：如果arr[0]的值大于0，将max赋值为arr[0]，否则赋值为0... 查看详情
剑指offer面试题42.连续子数组的最大和(代码片段)
问题描述面试题42.连续子数组的最大和输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例1:输入:nums=[-2,1,-3,4,-1,2,1,-5,4]输出:6解... 查看详情
返回一个二维整数数组最大子数组的和(代码片段)
...所有子数组的和的最大值。设计思路：参照一维整数数组求解最大子数组的方法，我们想着将二维数组通过行不同，列相加的方法转化为一维整数数组再求解最大子数组之和。具体实现：先求出每一行的最大子数组之和，之后比... 查看详情