dp(dynamic programming)
DP 是一种编程思想，主要用于解决最优解类型的问题。
其思路是为了求解当前的问题的最优解，使用子问题的最优解，然后综合处理，最终得到原问题的最优解。
但是也不是说任何最优解问题都可以DP，使用dp的问题一般满足下面的两个特征：
（1）最优子结构，就是指问题可以通过子问题最优解得到；体现为找出所有的子问题最优解，然后取其中的最优；
（2）重叠子问题，就是子问题是会重复的。而不是一直产生新的子问题（比如分治类型的问题）。 针对这个问题，先构建一个存储最大值的数组all all[i]表示从i到n-1之中的子数组的和的最大值
在构建一个数组start ，start[i]表示从i到n-1中包含nums[i]的子数组的和的最大值
最终我们要返回的值就是all[0]
通过dp思想我们可以得到从i=n-1到i=0 all[i]的最大值，那么all[0]就是最大的。
任意i all[i] = max（a[i+1],start[i]）
start[i] = max (nums[i],nums[i]+start[i+1]);
通过这两个式子进行循环就可以得到all[0]
int Max(int a,int b) { if(a>b) return a; return b; } int maxSubArray(vector<int>& nums) { int n=nums.size(); vector<int> all(n,0); vector<int> start(n,0); all[n-1]=start[n-1]=nums[n-1]; for(int i=n-2;i>=0;i--) { start[i]=Max(nums[i],start[i+1]+nums[i]); all[i]=Max(start[i],all[i+1]); } return all[0]; }
