最长上升子序列(一)

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        int len = arr.length;
        int[] dp = new int[len + 1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = Integer.MIN_VALUE;
         
        for(int i = 0; i < len; i++){
            for(int j = i; j >= 0; j--){
                if(arr[i] > dp[j]){
                    dp[j + 1] = Math.min(dp[j + 1],arr[i]);
                }
            }
        }
        int res = 0;
        for(int i = 1; i <= len ; i++){
            if(dp[i] >= Integer.MAX_VALUE ){
                break;
            }else{
                res = i;
            }
        }
        return res;
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        vector<int>res;
        int len = arr.size();
        for(int i=0;i<len;i++){
            if(res.size() == 0 || res.back() < arr[i]){
                res.push_back(arr[i]);
            }else{
                int j = res.size()-2;
                while(j>=0){
                    if(arr[i] > res[j])break;
                    j--;
                }
                res[j+1] = arr[i];
            }
        }
        return res.size();
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // 时间复杂度O(N^2)，空间复杂度O(N)
        if (arr.empty()) return 0;
        int res = 1;
        vector<int> dp(arr.size(), 1);
        for (int i = 1; i < arr.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[i] > arr[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                    res = max(res, dp[i]);
                }
            }
        }
        return res;
    }
};

class Solution:
    def LIS(self , arr: List[int]) -> int:
        res = 0
        n = len(arr)
        dp = [1 for i in range(n)]
        for i in range(1, n):
            for j in range(i):
                if arr[i] > arr[j] and dp[j]+1 > dp[i]:
                    dp[i] = dp[j]+1
                    res = max(res, dp[i])
        return res

#include <memory>
#include <vector>
class Solution {
  public:
    int LIS(vector<int>& arr) {
        vector<int>d(arr.size(),1);
        int ans=0;
        if(arr.size()==1||arr.size()==0){
            return arr.size();
        }
        for(int i=1;i<arr.size();i++){
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]&&d[i]<d[j]+1){
                    d[i]=d[j]+1;
                }
                ans=max(ans,d[i]);
            }
        }
        return ans;
    }
};

#define max(a,b) (a>b?a:b)
int LIS(int* arr, int arrLen ) {
    int dp[1000]={1}, res=1, i, j;
    if(arrLen==0)
        return 0;
    for(i=0; i<sizeof(dp)/sizeof(int); i++)
        dp[i] = 1;
    for(i=1; i<arrLen; i++) {
        for(j=0; j<i; j++) {
            if(arr[i]>arr[j]) {
                dp[i] = max(dp[i], dp[j]+1);
                res = max(res, dp[i]);
            }
        }
    }
    return res;    
}

在函数中，我们首先检查数组是否为空，如果为空，则返回0。然后，我们初始化一个dp数组，其长度与输入数组相同，并将所有元素初始化为1，因为每个元素本身可以看作是一个长度为1的子序列。

接下来，我们遍历输入数组，对于每个位置i，我们再遍历它之前的所有位置j，如果arr[i]大于arr[j]，说明我们可以将arr[i]添加到以arr[j]结尾的子序列中，从而可能形成一个更长的子序列。因此，我们尝试更新dp[i]为dp[j] + 1（即以arr[j]结尾的子序列长度加1）。

最后，我们返回dp数组中的最大值，它代表整个数组的最长严格上升子序列的长度。

class Solution:
    def LIS(self , arr: List[int]) -> int:
        # write code here
        if not arr: return 0
        dp = [1]*len(arr)
        for i in range(len(arr)):
            for j in range(i):
                if arr[i] > arr[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        if(arr.length == 1){
            return 1;
        }
        // 状态定义：dp[i]表示数组arr在第i个位置严格上升子序列的长度
        int dp[] = new int[arr.length];
        // 每个位置默认初始值为1
        Arrays.fill(dp,1);
        int res = 0;
        for(int i = 1;i < arr.length;i++){
            for(int j = 0;j < i;j++){
                // 状态转移
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
                res = Math.max(dp[i],res);
            }
        }
        return res;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        // 固定，以i结尾的最长的长度 dp[i], 往前去找所有小于它的dp[j]，找到后寻找出最大的
        int len = arr.length;
        if(len == 0) return 0;
        int[] dp = new int[len];
        for(int i = 0; i < len; i++) {
            dp[i] = 1;
        }
        int res = 1;
        for(int i = 1; i < len; i++) {
            for(int j = 0; j < i; j ++) {
                if(arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

class Solution {
public:

    int LIS(vector<int>& arr) {
        if(arr.size()==0) return 0;
        if(arr.size() == 1) return 1;
        int ans = 1;

        // 表示以 i 位置结尾的最长上升子序列
        vector<int> dp(arr.size(), 1);  
        for(int i=1;i<arr.size(); ++i){
            for(int j = 0; j<i; ++j){
                // 以 j 元素结尾的子序列 + 末尾元素i 也是严格递增的
                // 所以转移方程为 dp[i] = dp[j] + 1
                if(arr[j] < arr[i]){
                    dp[i] = max(dp[i], dp[j] + 1);
                    ans = max(ans, dp[i]); // 找到最大长度
                }
            }
        }
        return ans;
    }
};

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    func LIS ( _ nums: [Int]) -> Int {
        guard !nums.isEmpty else {
            return 0
        }

        // dp[i]表示0-i以第i个元素结尾的序列的最长上升子序列
        var dp: [Int] = Array(repeating: 1, count: nums.count)
        for i in 1 ..< nums.count {
            for j in 0 ..< i {
                if nums[j] < nums[i], dp[i] < dp[j] + 1 { // nums[i]和nums[j]构成上升的子序列且新的HLS大于以i结尾的HLS，即dp[i]，更新值
                    dp[i] = dp[j] + 1
                }
            }
        }
        return dp.sorted(by: { $0 < $1 }).last!
    }
}

function LIS(arr) {
    const n = arr.length;
    if (n === 0) return 0;
    const dp = new Array(n).fill(1);
    let max = 1;
    for (let i = 1; i < n; i++) {
        let j = i - 1;
        while (j >= 0 && j >= dp[i] - 1) {
            if (arr[j] < arr[i]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
                console.log(i, dp[i]);
            }
            j--;
        }
        if (dp[i] > max) {
            max = dp[i];
        }
    }
    return max;
}

#include "iostream"
#include "stdio.h"
#include <algorithm>
#include "vector"
using namespace std;
//问题描述：给出一个数字序列，求这个数字序列的一个严格递增子序列，且这个子序列长度最长
//法一：动态规划，本算法的时间复杂度是O(n^2),空间复杂度是O(n)
int LIS(vector<int> arr)
{
    int n=arr.size();
    if(n==0) return 0;
    vector<int> dp(n+1,1);//初值全部置为1，下面再解释
    for(int i=1;i<=n;i++)
    {
        //遍历arr[i]之前的每一个小于arr[i]的元素，比较
        for(int j=1;j<i;j++)
        {
            //状态转移方程：dp[i]=max(dp[j]+1,dp[i]),1<=j<i
            //需要注意的是，如果arr[i]之前的所有元素均不小于arr[i]，那么arr[i]就要置为1表示前i个元素中的最长上升子序列就是arr[i]元素自己
            //因为前i个元素中最小的就是自己了，例如序列12314，如果dp[4]=3,那么dp[5]=dp[4]+1=5,显然不合理
            if(arr[j-1]<arr[i-1])//数组下标是从0开始的，所以要减一
            dp[i]=max(dp[i],dp[j]+1);
        }
    }

    //循环赵dp数组中最大的那一个
    int mx=-1;
    for(int i=1;i<=n;i++)
    {
        mx=max(mx,dp[i]);
    }
    return mx;
}
//法二：贪心，最坏时间复杂度还是O(N^2)，但空间复杂度降低了一些（没有dp重复计算）

/*
算法原理：
1.创建一个空的辅助数组res，用于保存最长递增子序列。
2.遍历输入数组中的每个元素：
如果res为空或者当前元素大于res中的最后一个元素，将当前元素添加到res末尾，因为它可以延长最长递增子序列的长度。
否则，在res中寻找第一个小于当前元素的位置，并将该位置后面的元素替换为当前元素。这样做可以保持res中元素的有序性，并且能够在可能更小的元素出现时更新最长递增子序列。
3.返回res的长度作为最长递增子序列的长度。
*/


//此算法可以优化，在查找res数组中第一个小于arr[i]元素时，可以用二分查找，这样时间复杂度就变成O(nlogn)了
//此算法求得的长度一定是最优解，但是res这个数组不一定是正确的
int LIS2(vector<int>& arr) {
    vector<int>res;//保存最长递增子序列
    int len = arr.size();
    for(int i=0;i<len;i++)
    {
        //arr[i]比res尾更小，就直接把其接在后面
        if(res.size() == 0 || res.back() < arr[i])
        {
            res.push_back(arr[i]);
        }
        else//否则说明arr[i]比res尾部更小，那么把res中间的某个元素更新成arr[i]，就有可能获得更长的递增序列
        {
            int j = res.size()-2;//找到res的倒数第二个元素，开始从后往前遍历
            //在res中找到第一个小于arr[i]的元素res[j]，那么res[j+1]一定是第一个不小于arr[i]的元素，将其值替换为更小的arr[i]
            while(j>=0)
            {
                if(arr[i] > res[j])break;
                j--;
            }
            res[j+1] = arr[i];
        }
    }
    //验证输出
    for(int i=0;i<res.size();i++)
    {
        cout<<res[i];
    }
    cout<<endl;
    return res.size();
}
int main()
{
    vector<int> arr={2,3,4,1,4,5,2};
    cout<<LIS2(arr);

    return 0;
}

public int LIS (int[] arr) {
        //上升子序列，不连续，需要判断大小
        int[] dp=new int[arr.length];
        Arrays.fill(dp,1);
        if(arr.length==1) return 1;
        int ans=0;
        for(int i=1;i<arr.length;i++){
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            ans=Math.max(ans,dp[i]);
        } 
        return ans;
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        int n =arr.length;
        if (n < 2) {
            return n;
        }
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int result = 1;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] > arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}