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

参考代码:

import java.util.Scanner;
 
public class Main
{   public static void main(String[] args)
    {   Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n + 1];
        for(int i = 1; i <= n; i++)
            arr[i] = scanner.nextInt();
        scanner.close();
         
        int[] dp = new int[n + 1];
        int[] stack = new int[n + 1];
        int indexEnd = 0;//记录答案序列结尾数的下标
        int res = 0;
        for(int i = 1; i <= n; i++)
        {   dp[i] = 1;//arr[i]为一个序列
            for(int j = 1; j < i; j++)//以第i个数结尾的最大递增序列长度
            {   if(arr[j] <= arr[i] && dp[i] < dp[j] + 1)//arr[j] <= arr[i]，等于一定不能缺！！！
                    dp[i] = dp[j] + 1;
                if(dp[i] > res)
                {   res = dp[i];
                    indexEnd = i;
                }
            }
        }
        //构造答案序列
        int i = indexEnd - 1;
        int l = res;
        int index = 0;
        stack[index++] = indexEnd;
        while(l > 1)
        {   if(dp[i] == l - 1 && arr[i] <= arr[indexEnd])
            {   stack[index++] = i;
                indexEnd = i;
                l--;
            }
            i--;
        }
        System.out.println("max=" + res);
        for(int j = index - 1; j >= 0; j--)//逆序输出
            System.out.print(arr[stack[j]] + " ");
    }
}