引言
在C/C++面试或笔试中，字符串操作是常考内容，特别是对于其中的子串的操作，在各大公司的免试或笔试中均会有所涉及，本节针对求子串
字符串的最大连续子串的和
示例需求：
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。
求所有子数组的和的最大值。
要求:时间复杂度为O(n)O(n)，空间复杂度为O(n)O(n)
进阶:时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)
代码设计：
使用动态规划的方法进行。状态定义：temp[i]表示以i结尾的连续子数组的最大和。因此最终要求temp[n-1]状态转移方程：temp[i]=max(array[i],temp[i-1]+array[i])
解释：如果当前元素为整数，并且temp[i-1]为负数，那么当然结果就是只选当前元素技巧：这里为了统一代码的书写，定义temp[i]表示前i个元素的连续子数组的最大和，结尾元素为array[i-1]
测试用例如下：
示例1
输入：
[1,-2,3,10,-4,7,2,-5]
复制
返回值：
18
复制
说明：
经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
示例2
输入：
[2]
复制
返回值：
2
复制
示例3
输入：
[-10]
复制
返回值：
-10
intFindGreatestSumOfSubArray(vectorintarray)
{
intlen=array.size();
vectorinttemp(len+1,1);//定义temp[i]表示前i个元素的连续子数组的//最大和
temp[0]=0;
intres=array[0];
for(inti=1;i=len;++i)
{
temp[i]=max(array[i-1],temp[i-1]+array[i-1]);
res=max(res,temp[i]);
}
returnres;
}
结语
本节的内容并不复杂，做题的关键点是能够理解：temp[i]=max(array[i-1],temp[i-1]+array[i-1]);这条语句，表示的是前i个元素的连续子数组的最大和。