java--study||O.o--动态规划

看了大佬的题解：最长递增序列的长度就是第二个问题的答案

参考代码:

import java.util.ArrayList;
import java.util.Scanner;
 
public class Main
{   public static void main(String[] args)
    {   Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> arr = new ArrayList<>();
        while(scanner.hasNextInt())
            arr.add(scanner.nextInt());
        scanner.close();
         
        System.out.println(lengthOfLDS(arr));
        System.out.println(lengthOfLIS(arr));
    }
    static int lengthOfLDS(ArrayList<Integer> arr)//最长递减序列的长度
    {   int n = arr.size();
        int[] dp = new int[n];
        int maxLen = 1;
        for(int i = 0; i < n; i++)
        {   dp[i] = 1;
            for(int  j = 0; j < i; j++)
                if(arr.get(i) <= arr.get(j))//由题可知，可以相等
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
    static int lengthOfLIS(ArrayList<Integer> arr)//最长递减序列的长度
    {   int n = arr.size();
        int[] dp = new int[n];
        int maxLen = 1;
        for(int i = 0; i < n; i++)
        {   dp[i] = 1;
            for(int  j = 0; j < i; j++)
                if(arr.get(i) > arr.get(j))
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}