一、连续子数组的最大和
1、题目要求
2、个人题解
2.1、解题思路
首先我们要弄清楚题目的含义：什么是连续子数组？
子数组就是小数组里的元素，原数组里必须含义；加上连续，理解起来就是：该数组是原数组里的一串连续的元素或者单个元素。
搞清楚连续子数组后考虑该题的解法：
既然单个元素也属于连续子数组这个范畴，那么从第二个元素开始，我们对该元素和他与前一个元素的和比较，将二者中的较大值存到辅助数组dp中。
定义一个max作为最终的结果，并和数组dp中的元素不断对比，较大值将被赋值给max。
继续遍历，更新继续往dp数组中放入较大值，同时max也不断更新
遍历结束，max的值就是连续子数组的最大和
图示助理解：
2.2、代码实现
class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { if(array.size()==1) return *array.begin(); int dp[array.size()]; int max=array[0]; dp[0]=max; for(int i=1;i<array.size();i++){ int temp=dp[i-1]+array[i]; dp[i] = temp>array[i]? temp:array[i]; if(dp[i]>max) max=dp[i]; } return max; } };
2.3、代码解析
根据题目可知，数组长度是不小于1的，因此在长度为1的时候，直接返回即可
根据数组长度设置辅助数组dp的长度，初始化dp首元素和max的值为数组首元素的值
从第二个元素开始，将子数组和的最大值存入dp数组并更新max的值
遍历结束后，返回max，程序结束，问题解决。
二、连续子数组的最大和(二)
1、题目要求
2、个人题解
2.1、解题思路
该题是在连续子数组的和最大的基础上，返回该连续子数组，这里仍然使用动态规划来解题：
我们仍然要通过辅助数组dp来记录连续子数组的最大值，并根据最大值来更新连续子数组的区间，最后将最长区间作为数组下标，将区间范围的元素全部插入到要返回的数组中。
具体做法：
创建动态规划辅助数组，记录到下标i为止的最大连续子数组和，下标为0的时候，肯定等于原数组下标为0的元素。
准备左右区间双指针记录每次连续子数组的首尾，再准备两个双指针记录最大和且区间最长的连续子数组的首尾。
遍历数组，对于每个元素用上述状态转移公式记录其dp值，更新区间首尾（如果需要）。
出现一个最大值。且区间长度更大的时候，更新记录最长区间的双指针。
根据记录的最长子数组的位置取数组。
2.2、代码实现
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> FindGreatestSumOfSubArray(vector<int>& array) { // write code here if(array.size()==1) return array; vector<int>res; vector<int> dp(array.size(),0); dp[0]=array[0]; int ans=dp[0]; //滑动区间 int left=0,right=0; //最终的区间范围 int resl=0,resr=0; for(int i=1;i<array.size();i++){ right++; //状态转移：连续子数组的最大值 dp[i]=max(dp[i-1]+array[i], array[i]); //区间新起点 if(dp[i-1]+array[i]<array[i]) left=right; //更新最大值 if(dp[i]>= ans) { ans=dp[i]; resl=left; resr=right; } } //给res数组插入数据 for(int i=resl;i<=resr;i++) res.push_back(array[i]); return res; } };
2.3、代码解析
根据题目可知，数组长度是不小于1的，因此在长度为1的时候，直接返回即可
根据数组长度初始化辅助动态数组dp，最大值记为ans且默认为数组首元素的值
声明遍历的区间以及最终的区间并初始化为0
进入for循环，右区间right递增，将最大连续子数组的和存到dp数组中。
如果是相加结果没有自身对应的元素值大，那么right将作为新区间的起点，即：left=right
每次新存入dp数组的元素组和最大值ans比较：
如果dp内的数据大，那么就更新最大值并让最终的区间等于遍历的区间
如果dp内的数据小，不进行操作，最终区间范围不变
随着遍历的进行，最终区间不断变化，遍历结束时，最终区间也就确定了下来
最后根据区间将数组中的数据插入到ans数组中并返回
三、动态规划知识学习
动态规划算法的基本思想是：
将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；
对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。
动态规划算法将问题的解决方案视为一系列决策的结果。
