题解 | #HJ103 Redraiment的走法#

最长上升子串

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            int [] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scan.nextInt();
            }
            Map<String, StringBuffer> max = new
            HashMap<String, StringBuffer>();//用arraylist不好输出，map+arraylist这里调试不了
            StringBuffer masSeq = new StringBuffer();
            masSeq.append(String.valueOf(a[0]));
            max.put(String.valueOf("0"), masSeq);
            for (int i = 1 ; i < n; i++) {//以第i个数为尾的最长上升子串
                int maxtemp = 0;
                int maxlength = 0;
                out:
                for (int j = i - 1 ; j >= 0; j--) {

                    StringBuffer maxSeqTemp1 = new StringBuffer(max.get(String.valueOf(j)));////StringBuffer新建赋值必须得new，不然用的就是被赋值的字符串的地址
                    if (j == 0 && a[i] <= a[j] &&
                            maxtemp == 0) {//如果不存在可延续前继记忆串，即第一个数都都比a[i]大，以a[i]开始重建新串

                        StringBuffer maxSeqTemp2 = new StringBuffer(String.valueOf(
                                    a[i]));//这个条件(所在if注释)，包括第i个数，且以第i个数为尾的最长上升子串就是a[i]
                        max.put(String.valueOf(i), maxSeqTemp2);
                        for (int k = 0 ; k < maxSeqTemp2.length(); k++) {
//                             System.out.println(i + "+:" + maxSeqTemp3.get(k));
                        }
                        break out;
                    } else if (a[i] > a[j] && maxlength < maxSeqTemp1.length()) {//寻找最长前继串的尾坐标
                        maxtemp = j + 1;
                        maxlength = maxSeqTemp1.length();
                    }
                    if (j == 0 && maxtemp > 0) {//如果遍历到了第一个数，且a[i]可以找到前继延长串的点（动态规划点）
                        StringBuffer maxSeqTemp3 = new StringBuffer(max.get(String.valueOf(
                                    maxtemp - 1)));
                        maxSeqTemp3.append(",").append(String.valueOf(
                                              a[i]));//这个条件(所在if注释)，以第i个数为尾的最长上升子串长度，为前面最长可延伸记忆串长度加1，“,”用来区分长度大于1的数
                        max.put(String.valueOf(i), maxSeqTemp3);
                        break out;
                    }
                }
            }
            int maxlength2 = 0 ;
            for (int i = 0 ; i < max.size(); i++) {
//                 System.out.println(max.get(String.valueOf(i)));
                String [] smaxarray= max.get(String.valueOf(i)).toString().split(",");
                 if (maxlength2<smaxarray.length){
                     maxlength2 = smaxarray.length;
                 }
            }
            System.out.println(maxlength2);
        }
    }
}