先放题目

题目描述：给定一个无序的整数数组，找到其中最长上升子序列

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

首先我们需要明白子序列的概念，子序列不等同于子串，子串一定是连续的，子序列不一定是连续。

数学归纳法

动态规划的核心设计思想是数学归纳法。

比如我们想证明一个数学结论，那么我们先假设这个结论在k<n时成立，然后根据这个假设，想办法推导证明出k=n的时候结论也成立。如果证明的出来，说明这个结论对于k等于任何数都成立。

解题推算

在本题中，我们可以根据数学归纳法的设计思想，假设dp[0…i-1]都已经算出来了，然后根据前面的结果算出dp[i].

那我们定义dp[i]表示以nums[i]这个元素结尾的最长递增子序列的长度。

根据这个定义我们可以知道

• dp[i]的初始值都为1，因为以nums[i]结尾的最长递增子序列起码要包含它自己。
• 最终结果为dp数组的最大值，可以建立一个max变量保存当前最大值

那我们如何根据dp[0…i-1]求出dp[i]嘞

• 我们可以找前面那些结尾比nums[i]小的子序列，然后选择最长的那个加1即为dp[i]的值

实现代码

var lengthOfLIS = function(nums) {
    let max=1
    let dp=Array(nums.length).fill(1)
    for(let i=0;i<nums.length;++i){
        for(let j=0;j<i;++j){
            if(nums[i]>nums[j]){
                dp[i]=Math.max(dp[i],dp[j]+1)
            }
        }
        max=Math.max(max,dp[i])
    }
    return max
};

再来一刀

题目描述：给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

解题分析

这道题其实就是最长递增子序列的变种，因为每次合法的嵌套相当于就是在找一个最长递增子序列，难点在于这次是在二维数组里面找。

我们先对宽度w进行升序排序，如果遇到w相同的情况，则按高度进行降序排序.因为两个宽度相同的信封不能相互包含，而逆序排序可以保证在W相同的数对中最多选取一个计入LIS。排序后，我们把所有的H作为一个数组进行计算LIS，结果就是这道题的答案

对给的数对进行排序

在h上寻找最长递增子序列

实现代码

var maxEnvelopes = function (envelopes) {
    envelopes.sort((a, b) => {
        return a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]
    })
    let nums = []
    let n = envelopes.length
    for (let i = 0; i < n; i++) {
        nums.push(envelopes[i][1])
    }
   return lengthOfLIS(nums)
};
function lengthOfLIS(nums) {
    let max=1
    let dp=Array(nums.length).fill(1)
    for(let i=0;i<nums.length;++i){
        for(let j=0;j<i;++j){
            if(nums[i]>nums[j]){
                dp[i]=Math.max(dp[i],dp[j]+1)
            }
        }
        max=Math.max(max,dp[i])
    }
    return max
};

好兄弟，再来一刀

上题目，已麻目

题目描述：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

解析分析

好家伙，这怎么又跟数学归纳法联系上了呢

假设我们已经算出了dp[i-1],如何推导出dp[i]呢，这是个问题

dp[i]有两个选择，要么与前面的相邻子数组链接，要么不与它连接，自成一派，我们取结果更大的那个。

之前的dp都是数组，但这道题中dp[i]只与dp[i-1]有关系，我们可以压缩成两个变量dp0,dp1。

我们还要设一个变量res保存遍历过程中的最大值

实现代码

var maxSubArray = function(nums) {
    let n=nums.length
    if(n==0){
        return 0
    }
    let dp0=nums[0]
    let dp1=0,res=dp0
    for(let i=1;i<n;i++){
        dp1=Math.max(dp0+nums[i],nums[i])
        dp0=dp1
        res=Math.max(res,dp1)
    }
    return res
};