从简单的题开始吧，希望自己可以坚持每天打卡，羊企鹅加油鸭！
这周预计多写写动态规划类。
题目描述
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
来源：leetcode
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/
拿到这题最开始的思路是DP，想了一下有点思路就去看讨论，发现自己的DP复杂度太高了。。。。
最初的想法是： Dp,q=max(Dp+1,q+num[p], Dp,q-1 +num[q]) ，来求D0,length
感觉这样好像有点类似分冶法的思路了。
然后去看了大神的思路，总结一下如下三种解法：
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 类贪心算法 | O(n) | O(1) |
| 动态规划法 | O(n) | O(1) |
| 分冶法 | O(nlgn) | O(1) |
一、贪心算法
emmm 个人觉得这并不是严格的贪心算法，因为贪心算法要求局部总是最优的，而这里的要求是整个子数组的和是最大的。不过我们可以借鉴贪心的思路，即，到当前为止，求到的解总是最优的，具体思路如下：
1.从前向后遍历数组，假设已经求得遍历过的数中的最大和数组，我们可以把这个最大和数组记为一个整形结果：Di-1。对任意i，若要使得结果最优，一定有：Di-1>=0。
2.对下一个要取到的数num[i]，若为非负数，那么情况很简单，Di=（Di-1+num[i]）>=Di-1，取第i个数，使得我们的子数组和变大；
若为负数，那么情况变得有点复杂：
1.若这个负数，使得Di=（Di-1 +num[i]<0）<=Di-1，即有:Di<0,那么应记录下Di-1,并舍弃该Di，从第i+1重新开始计算最大和数组并与Di-1比较。
2.若第i个数加上后，有：Di=（Di-1+num[i])>0,那么不需要舍弃该Di，继续向后遍历，看看有没有能累加到比Di-1更大的子数组（所以为什么说这个算法不是严格的贪心，因为在这个时候并不是最优解）
代码如下：
int maxSubArray(vector<int>& nums) {
int max=0;//max为记录的最大和
int now=0;//now为当前记录值
int nummax=nums[0];//用nummax来记录数组中最大的数以防止全为负数时输出错误（全为负数则需输出最小的负数
int len=nums.size();
for(int i=0;i<len;i++)
{
if(now+nums[i]<0)
now=0;
else
{
now=now+nums[i];
}
nummax=nummax>nums[i]?nummax:nums[i];
max=max>now?max:now;
}
if(nummax<0) return nummax;
else return max;
}
正如同上面的分析，这并不是一个典型的贪心问题，只是用了一点点贪心的思路
二、动态规划算法
emmm每次知道要用动态规划，但是构造的状态定义递推式都不是很动态规划，多思考多总结一下我和标答的差距
状态定义：Dp[i]表示到i为止（包含i)，产生的最大子数组和的值。
初始状态：Dp[0]=nums[0]
状态转移：对Dp[i+1],由于Dp[i+1]必须包含nums[i+1],那么其实只要考虑Dp[i]的值就可以了：
- Dp[i]<0，那么Dp[i+1]=nums[i+1]
- Dp[i]>=0，那么Dp[i+1]=nums[i+1]+Dp[i]
故Dp[i]=max(nums[i],nums[i+1]+Dp[i-1]
最终状态：Dp[length]即为所求数组的最大和子数组
图解来源：Karhets的题解
代码如下：
int maxSubArray(vector<int>& nums) {
int i,dp,max;
dp=nums[0];
max=dp;
int len=nums.size();
for (i=1;i<len;i++)
{
if(dp<0)
dp=nums[i];
else
{
dp=dp+nums[i];
}
max=max>dp?max:dp;
}
return max;
}
执行了一下居然比上面的伪贪心算法复杂度还高，又修改了一下(实际上没太多区别)：
int maxSubArray(vector<int>& nums) {
int i,dp,max;
dp=nums[0];
max=dp;
int len=nums.size();
for (i=1;i<len;i++)
{
dp=dp>0?dp+nums[i]:nums[i];
max=max>dp?max:dp;
}
return max;
}
三、分冶法
待补充
