题解 | #合唱队形#

最高峰可能在中间，也可能在两边，求最大值

public static Integer dp(int b[]) {

        int []b1 = new int[b.length];  //左至右递增

        int []b2 = new int[b.length];  //右至左递增

        b1[0] = 1;

        b2[b2.length - 1] = 1;

        int max = 0;

        for (int i = 1; i < b.length; i++) {

            b1[i] = 1;

            b2[b.length - i - 1] = 1;

            for (int j = i - 1; j >= 0 ; j--) {

                if (b[i] > b[j])

                    b1[i] = Math.max(b1[j] + 1,b1[i]);

                if (b[b.length - 1 - i] > b[b.length - i + j])

                    b2[b.length - 1 - i] = Math.max(b2[b.length - i + j] + 1,b2[b.length - 1 - i]);

            }

        }

        for (int i = 0 ; i < b.length ; i ++) {

            max = Math.max(b1[i] + b2[i], max);   //中间最大  中间 - 1

        }

        max = Math.max(max-1, Math.max(b1[b.length - 1], b2[0]));     //边缘最大  

        return b.length - max;

    }