当前位置:网站首页>Longest increasing subsequence

Longest increasing subsequence

2022-06-11 02:57:00 ambition_ forever

package LongestIncrSub;

import java.util.Arrays;
import java.util.HashSet;

/**
 *  Function description 
 *  The longest increasing subsequence 
 */
public class Main {

    public static void getLongestIncrSub(int[] arr) {
        int len = arr.length;
        int[] dp = new int[len];
        int[] res = new int[len];
        Arrays.fill(dp, 1);
        Arrays.fill(res, 0);

        int maxNum = arr[0];
        int maxDp = 0;

        for (int i = 0; i < len; i++) {
            maxNum = Math.max(maxNum, arr[i]);
            for (int j = i; j >= 0; j--) {
                if (arr[i] > arr[j]) {
                    dp[i] = 1 + dp[j];
                    res[i] = arr[j];
                    maxDp = Math.max(maxDp, dp[i]);
                    break;
                }

            }
        }

        HashSet<Integer> resSet = new HashSet<>();
        for (int redI : res) {
            if (redI == 0) {
                continue;
          
原网站

版权声明
本文为[ambition_ forever]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/162/202206110232211971.html