300/674-最长上升子序列/子数组

LeetCode 300. Longest Increasing Subsequence

LeetCode-300

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

method

子序列不要求连续

dp[i]：以nums[i]结尾所能得到的最长上升子序列长度

j从0到i-1遍历，如果nums[i] > nums[j]，那就可以在nums[j]的子序列后面加上nums[i]，所以dp[i]就在dp[j]的基础上加1，所以递推公式是

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

单个元素都是长度为1的递增子序列，所以dp数组初始化为1

int lengthOfLIS(vector<int>& nums) {
    if (nums.size() <= 1) return nums.size();
    vector<int> dp(nums.size(), 1);
    int res = 0;
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
        }
        res = max(res, dp[i]);  // 还要对dp[i]取最大值
    }
    return res;
}

因为dp[i]表示nums[i]结尾的最大递增长度，所以最大值可能在中间

nums: [1,3,6,7,9,4,10,5,6]
dp:    1 2 3 4 5 3  6 4 5     max=6 

---

LeetCode 674. Longest Continuous Increasing Subsequence

LeetCode-674

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

Example 1:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

method

dp[i]：以nums[i]结尾的最长连续递增子数组长度

因为要求连续，所以就不用从头开始比较，只要比较nums[i]和nums[i-1]就可以了，递增就dp[i]=dp[i-1]+1

dp数组全部初始化为1就可以

int findLengthOfLCIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    int res = dp[0];
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[i - 1]) 
            dp[i] = dp[i - 1] + 1;
        res = max(res, dp[i]);  // 记录最大的dp[i]
    }
    return res;
}

只跟前一个状态有关，可以只用两个变量

int findLengthOfLCIS(vector<int>& nums) {
    int res = 1;
    int dp0 = 1;
    int dp1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[i - 1]) dp1 = dp0 + 1;
        else dp1 = 1;   // 否则连续就断了，要重新开始
        res = max(res, dp1);
        dp0 = dp1;
    }
    return res;
}