最大子数组和

如果定义dp[i]为0到i内最大子数组和，那求解就很难了
正确答案为以i结尾的最大子数组和，那么状态转移方程就很容易得出：dp[i+1]=max{dp[i]+a[i+1], a[i]}
类似的题还有最长连续递增子数组

最长上升子序列

法一：n*n的动态规划

  1. class Solution {
  2. public:
  3.     int lengthOfLIS(vector<int>& nums) {
  4.         vector<int> dp;
  5.         dp.resize(nums.size());
  6.         dp[0]=1;
  7.         int res = 1;
  8.         for(int i=1;i<nums.size();i++) {
  9.             dp[i] = 1;
  10.             for(int j=0;j<i;j++) {
  11.                 if(nums[j]<nums[i]) dp[i]=max(dp[i], dp[j]+1);
  12.             }
  13. //            cout<<i<<' '<<dp[i]<<endl;
  14.             res = max(res,dp[i]);
  15.         }
  16.         return res;
  17.     }
  18. };

法二：n*logn的贪心

  1. 让序列上升地尽可能慢，以输入序列[0,8,4,12,2] 为例：
  2. 第一步插入 00，d = [0]d=[0]
  3. 第二步插入 88，d = [0, 8]d=[0,8]
  4. 第三步插入 44，d = [0, 4]d=[0,4]
  5. 第四步插入 1212，d = [0, 4, 12]d=[0,4,12]
  6. 第五步插入 22，d = [0, 2, 12]d=[0,2,12]。