本题leetcode题解
======================================================================================
使用动态规划求解连续子数组问题的时需要注意什么呢？
首先，对dp数组的定义是什么？ 一般从题目入手，我一开始会把**dp[i]**定义为nums【0,…,i】中的最大子数组和。当你没有把握的时候，就带着写的这个定义去计算一下，看看是否能通过dp的定义顺利的转移出下一个状态。
很快你就会发现, 将dp定义成nums【0,…,i】中的最大子数组和是行不通的。因为题目很明显要问你连续的情形，很有可能dp【4】的最大子数组和是由nums的第一位和第二位组成的，这种情况下，对于dp【5】来说，怎么能写出符合连续状态的转移呢？
因此，我们需要修改dp数组的定义。 将dp【i】定义为以nums【i】结尾的最大子数和。这样就完美解决，有了结尾数的保证，那么对于当前的dp【i】我们要考虑的选择无非就是两个。
因此给出代码：
class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); if(n==0) return 0; vector<int> dp(n,0); dp[0] = nums[0]; for(int i = 1;i<nums.size();i++){ dp[i] = max(dp[i-1]+nums[i],nums[i]); } int res = INT_MIN; for(int i = 0;i<nums.size();i++){ res = max(res,dp[i]); } return res; } };当考虑dp数组的含义的时候，一定要扣紧题目，连续这一字眼已经能给出求解方向。
======================================================================================
很明显又是一道动态规划求解的题目。再明确dp数组之前，我们先分析下这道题和上一道的区别，看看能不能带来些做题的启示。 Leetcode 53 给出的提出说明时， O(n)的解法，很好解释，因为我们要求解的对象是连续子数组，那么【i】位置的答案只会与【i-1】位置的答案联系起来。因此遍历一遍，就是填完了答案的过程。
但是leetcode 300，子序列就需要注意了，序列！序列！ 只要元素是来自原序列就可以的，即中间是可以断开的。因此我们意识到，【i】位置的答案需要通过依次判定【0,…,i-1】（其前面元素）的情况才能确定。这不就是O(n^2)嘛！
因此，来定义这道题的dp数组的含义，既然题目要求了上升子序列，那么我们要扣住 上升这一要求，也就是当前的元素nums【i】可以接在某个上升序列的后面（假设这个上个上升序列的最后元素位置在j），那就得满足nums【i】> nums【j】。这部就有点转移的味道了。
因此nums【i】得和其前面的元素进行比较，找出最长的那个上升序列。
在这里插入代码片 ```class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; vector<int> dp(n,1); //注意：初始化为1，默认序列只有自己一个元素，最小也是1 for(int i = 1;i<n;i++){ for(int j = 0;j<i;j++){ if(nums[i]>nums[j]） dp[i] = max(dp[i],dp[j]+1); //状态转移方程 } } int res = 0; for(int i = 0;i<n;i++) res = max(res,dp[i]); return res; } };