public class arrDemo {
 public static void main(String[] args) {
  // int[] arr = {89, 256, 78, 1, 46, 78, 8};
  int[] arr = { 1, 3, 5, 2, 4, 6, 7, 8 };
  // int[] arr = {6, 4, 8, 2, 17};
  int max = 0;
  int maxLen = arr.length;
  // 從后往前遍歷數組，分別求出以arr[i]結尾的時候的最長子序列長度
  for (int i = arr.length - 1; i > 0; i--) {
   int[] newArr = new int[i];
   System.arraycopy(arr, 0, newArr, 0, i);
   int currentLength = 1 + dp(newArr, arr[i]);
   if (currentLength > max)
    max = currentLength;
   // 最長子序列的長度最長為原始數組的長度，
   // 因為不需要我們求最長子序列的元素，所以直接結束循環(huán)，減少時間開銷
   if (max == maxLen)
    break;
  }
  System.out.println(max);
 }
 public static int dp(int[] arr, int end) {
  // 遞歸結束條件
  if (arr.length == 1) {
   // 小于end則包含在子序列中，子序列長度+1
   if (arr[0] <= end)
    return 1;
   else
    return 0;
  }
  // 遍歷數組，找到最靠近end的并且<=end的元素位置i
  for (int i = arr.length - 1; i >= 0; i--) {
   if (arr[i] <= end) {
    // 從i處截斷數組，將arr[0]到arr[i-1]組成新數組繼續(xù)遞歸求長度
    int[] newArr = new int[i];
    System.arraycopy(arr, 0, newArr, 0, i);
    // 分別計算包含arr[i]時的最長子序列和不包含arr[i]時的最長子序列，取最大值
    int containLen = dp(newArr, arr[i]) + 1;
    int notContainLen = dp(newArr, end);
    return containLen > notContainLen ? containLen : notContainLen;
   }
  }
  // 如果沒找到比end更小的，返回長度為0
  return 0;
 }
}