合唱队

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

private static int minTest(int[] heights){

    int n = heights.length;

    int[] ldp = new int[n];

    int[] rdp = new int[n];

    for(int i= 0;i<n;i++){

        ldp[i] = 1;

        for(int j = 0;j<i;j++){

            if(heights[i]>heights[j]){

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

            }

        }

    }

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

        rdp[i] = 1;

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

            if(heights[i]>heights[j]){

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

            }

        }

    }

    // 找到一个同学使得左侧和右侧最长递增子序列长度之和最大

    int res = 0;

    for(int i = 0;i<n;i++){

        res = Math.max(res,rdp[i]+ldp[i]-1);

    }

    return n-res;

}

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[] heights = new int[n];

    for(int i = 0;i<n;i++){

        heights[i] = sc.nextInt();

    }

    int res = minTest(heights);

    System.out.println(res);

}

}

import java.util.Scanner;
import java.util.Arrays;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.nextLine();
        String input = sc.nextLine();
        String[] arr = input.split(" ");
        int[] src = Arrays.stream(arr).mapToInt(Integer::parseInt).toArray();
        // 求left
        int[] left = new int[arr.length];
        for (int i = 0; i < src.length; i++) {
            left[i] = 0;
            for (int j = 0; j < i; j++) {
                if (src[j] < src[i]) {
                    left[i] = Math.max(left[i], left[j] + 1);
                }
            }
        }
        // 求right
        int[] right = new int[arr.length];
        for (int i = src.length - 1; i >= 0; i--) {
            right[i] = 0;
            for (int j = src.length - 1; j > i; j--) {
                if (src[j] < src[i]) {
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }
        // 汇总
        int[] res = new int[src.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = left[i] + right[i] + 1;
        }
        int result = arr.length - Arrays.stream(res).max().orElse(0);
        System.out.println(result);
    }
}

最长上升子序列 + 最长下降子序列， 二分

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            // 选 第 i 位 不出列 求左右两边严格最长上升和递减子序列长度
            // 结果为 两边长度之和加上中间这位的最大值， n - mx 就是要出列的人数
            int up = maxUp(a, 0, i - 1);
            int dn = maxDn(a, i + 1, n - 1);
            int s = up + dn + 1;
            if (s > mx) {
                mx = s;
            }
        }
        System.out.println(n - mx);
    }
    static int maxUp(int[] a, int l, int r) {
        if (l > r){
            return 0;
        }
        int[] dp = new int[r - l + 1];
        int len = r - l + 1;
        int pos = 0;
        for (int i = l; i <= r; ++i) {
            if (pos == 0 || a[i] > dp[pos - 1]) {
                dp[pos ++] = a[i];
            } else {
                int p = bs1(dp, 0, pos - 1, a[i]);

                dp[p + 1] = a[i];
            }
        }
        return pos - 1;
    }
    static int bs1(int[] a, int l, int r, int x) {
        int p = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (a[mid] < x) {
                p = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        return p;
    }
    static int maxDn(int[] a, int l, int r) {
        if (l > r){
            return 0;
        }
        int[] dp = new int[r - l + 1];
        int len = r - l + 1;
        int pos = 0;
        for (int i = l; i <= r; ++i) {
            if (pos == 0 || a[i] < dp[pos - 1]) {
                dp[pos ++] = a[i];
            } else {
                int p = bs2(dp, 0, pos - 1, a[i]);
                dp[p + 1] = a[i];
            }
        }
        return pos;
    }
    static int bs2(int[] dp, int l, int r, int x){
        int p = -1;
        while (l <= r){
            int mid = (l + r) / 2;
            if (dp[mid] > x){
                l = mid + 1;
                p = mid;
            }else r = mid - 1;
        }
        return p;
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = sc.nextInt();
            sc.nextLine();  //防止回车符号 "/n 被计入下一个输入中,只有while(sc.hasNextLine())时候需要注意这里,
                            //其他的sc.hasNext()或者sc.hasNextInt()都不用在这里写这一行
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            sc.nextLine();  //防止回车符号 "/n 被计入下一个输入中

            //左边最长递增子序列
            int[] dp1 = new int[n];
            for (int i = 0; i < n; i++) {
                dp1[i] = 1;     //全元素赋值为1
                for (int j = 0; j < i; j++) {
                    if (a[j] < a[i]) {
                        dp1[i] = Math.max(dp1[j] + 1, dp1[i]);//此处dp1[j] + 1中的+1指的是i位置元素          选↓        不选↓
              //同理01背包问题，当发现左侧有比a[i]小的元素时，我们可以选该元素作子序列元素，也可以不选。Math.max(dp1[j] + 1, dp1[i])
                    }
                }
            }

            //右边最长递减子序列
            int[] dp2 = new int[n];
            for (int i = n - 1; i >= 0; i--) {//右边要找递减子序列，所以注意倒序
                dp2[i] = 1;
                for (int j = n - 1; j > i; j--) {
                    if (a[j] < a[i]) {
                        dp2[i] = Math.max(dp2[j] + 1, dp2[i]);
                    }
                }
            }
            int res = 1;
            for (int i = 0; i < n; i++) { //计算每个预设位置i的最长子序列 = 左 + 右 - 1
                a[i] = dp1[i] + dp2[i] - 1;
                if (a[i] > res) {
                    res = a[i];
                }
            }
            System.out.println(n - res); //总人数减去最长子序列元素个数，也就是组成合唱团的人数，就得到了需要出列的人数 
        }
        sc.close();
    }
}

最一开始没想到是动态规划,直接做的时候发现跟想的不一样,直接去评论区发现是动态规划问题

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int num = in.nextInt();
            int[] arr = new int[num];
            for (int i = 0; i < num ; i++) {
                arr[i] =  in.nextInt();
            }
            //左到右升序
            int[] left = new int[num];
            for (int i = 0; i < num ; i++) {
                left[i] = 1;//当前位置的数已经计数了 计数1
                for (int j = 0; j < i ; j++) {
                    //内循环在当前位置以内  注:arr [i]为当前索引数据, arr[j] 是arr [i]左边的数据
                    if (arr[j] < arr [i]) {
                        left[i] = Math.max(left[j] + 1, left[i]);
                    }
                }
            }
            //右到左升序
            int[] right = new int[num];
            for (int i = num - 1 ; i >= 0 ; i--) {
                right[i] = 1;//当前位置的数已经计数了 计数1
                for (int j = num - 1; j > i ; j--) {
                    //内循环在当前位置以内  注:arr [i]为当前索引数据, arr[j] 是arr [i]右边的数据
                    if (arr[j] < arr [i]) {
                        right[i] = Math.max(right[j] + 1, right[i]);
                    }
                }
            }
            int max = 0;
            for(int i= 0;i< num; i++){
                max = Math.max(left[i] + right[i] -1,max);// left[i] = 1; right[i] = 1; 导致当前索引的那个人多计数一次
            }

            System.out.println(num - max);
        }
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int length = in.nextInt();
            int[] arr = new int[length];

            for (int i = 0; i < length; i++) {
                arr[i] = in.nextInt();
            }

            int[] left = new
            int[length]; // 每个节点向左递减最大的子序列长度
            int[] right = new
            int[length];// 每个节点向右递减最大的子序列长度

            // 初始化两个数列，全设置为1
            for (int i = 0; i < length; i++) {
                left[i] = 1;
                right[i] = 1;
            }

            for (int i = 0; i < length; i++) {
                for (int j = 0; j < i; j++) {
                    if (arr[i] > arr[j]) {
                        left[i] = Math.max(left[i], left[j] + 1);
                    }
                }
            }

            for (int i = length - 1; i > -1; i--) {
                for (int j = i + 1; j < length; j++) {
                    if (arr[i] > arr[j]) {
                        right[i] = Math.max(right[i], right[j] + 1);
                    }
                }
            }

            int maxNum = 0;
            int[] tempArr = new int[length];
            for (int i = 0; i < length; i++) {
                tempArr[i] = left[i] + right[i] - 1;
                maxNum = Math.max(tempArr[i], maxNum);
            }
            System.out.println(length - maxNum);

        }
        in.close();
        ;
    }
}

package HW;

import java.util.Scanner;

public class HJ24 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] ints = new int[n];
            for (int i = 0; i < n; i++) {
                ints[i] = in.nextInt();
            }
            int max = Integer.MAX_VALUE;
            // dp缓存
            int[][] dp = new int[n][n];
            for (int i = 0; i < n; i++) {
                // 以i为中心，检查左右
                int leftRes = checkLeft(i, i - 1, ints, dp);
                int rightRes = checkRight(i, i + 1, ints, dp);
                if (max > leftRes + rightRes) {
                    max = leftRes + rightRes;
                }
            }
            System.out.println(max);
        }
    }

    private static int checkRight(int cur, int right, int[] ints, int[][] dp) {
        if (cur >= ints.length || right >= ints.length) return 0;
        if (dp[cur][right]!=0)return dp[cur][right];
        // 比cur大，则必须出列
        if (right < ints.length && ints[right] >= ints[cur]) {
            int res = 1 + checkRight(cur, right + 1, ints,dp);
            dp[cur][right] = res;
            return res;
        } else {
            // 比cur小，不一定不出列
            // 尝试出列， 可能有这种情况：5，2，4，3，则2出列比不出列好
            int out = 1 + checkRight(cur, right + 1, ints,dp);
            // 尝试不出列
            int noOut = checkRight(right, right + 1, ints,dp);
            int res = Math.min(out, noOut);
            dp[cur][right] = res;
            return res;
        }
    }
    
    private static int checkLeft(int cur, int left, int[] ints, int[][] dp) {
        if (left < 0 || cur < 0) return 0;
        if(dp[cur][left]!=0) return dp[cur][left];
        if (left >= 0 && ints[left] >= ints[cur]) {
            int res = 1 + checkLeft(cur, left - 1, ints,dp);
            dp[cur][left] = res;
            return res;
        } else {
            // 比cur小，不一定不出列
            // 尝试出列， 可能有这种情况，3，4，2，5，则2出列比不出列好
            int out = 1 + checkLeft(cur, left - 1, ints, dp);
            // 尝试不出列
            int noOut = checkLeft(left, left - 1, ints, dp);
            int res = Math.min(out, noOut);
            dp[cur][left] = res;
            return res;
        }
    }
}

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        // int nums[]={1,4,3,4,2,1,5,3};
        int nums[]=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=sc.nextInt();
        }
        int[] dp1 = maxIncr(nums);
        int[] dp2 = maxDecr(nums);
        // System.out.println(Arrays.toString(dp1));
        // System.out.println(Arrays.toString(dp2));
        int[] dp3=new int[nums.length];
        int max=0;
        for(int i=0; i<nums.length; i++){
            dp3[i] =dp1[i]+dp2[i]-1;//最长 +最短-自己重复的一次
            max=Math.max(max,dp3[i]);
        }
        System.out.println(n-max);

    }
    //最长递增子序列
   //dp1= [1, 1, 1, 2, 2, 1, 3, 4]
    private static int[] maxIncr(int[] nums) {
        int dp[]=new int[nums.length];
        dp[0]=1;
        for(int i = 1; i< nums.length; i++)
        {
            int max=0;
            for(int j=0;j<i;j++){
                if(nums[i]> nums[j]){
                    max=Math.max(max,dp[j]);
                }
        }
            dp[i]=max+1;
        }
        return dp;
    }
    //最长递减子序列
    //dp2[]=[3, 3, 2, 3, 2, 1, 1, 1]
    private static int[] maxDecr(int[] nums) {
        int dp[]=new int[nums.length];
        dp[nums.length-1]=1;
        for(int i = nums.length-1; i>=0; i--)
        {
            int max=0;
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]> nums[j]){
                    max=Math.max(max,dp[j]);
                }
            }
            dp[i]=max+1;
        }
        return dp;
    }
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] height = new int[n];
            for (int i = 0; i < n; i++) {
                height[i] = in.nextInt();
            }
            System.out.println(dp(height));
        }
    }

    private static int dp(int[] height) {
        int n = height.length;
        int min = n;
//        dp[i]: 以i结尾的最长上升子序列数量（不包括dp[i]）
        int[] dpLas = new int[n];
//        dp[i]: 以i开头的最长下降子序列数量（不包括dp[i]）
        int[] dpLds = new int[n];
        for (int i1 = 0, i2 = n - 1; i1 < n; i1++, i2--) {
//            先求最长上升子序列
            for (int j = 0; j < i1; j++) {
                if (height[j] < height[i1]) {
                    dpLas[i1] = Math.max(dpLas[i1], dpLas[j] + 1);
                }
            }
//            求最长下降子序列
            for (int j = n - 1; j > i2; j--) {
                if (height[j] < height[i2]) {
                    dpLds[i2] = Math.max(dpLds[i2], dpLds[j] + 1);
                }
            }
        }
        for (int i = 0; i < n; i++) {
//            +1 是包括自身元素
            min = Math.min(n - (dpLds[i] + dpLas[i] + 1), min);
        }
        return min;
    }
}

import java.util.Scanner;

/**
 * 描述
 * N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形
 * 通俗来说，能找到一个同学，他的两边的同学身高都依次递减的队形就是合唱队形。
 * 例子：
 * 123 124 125 123 121 是一个合唱队形
 * 123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求
 * 123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。
 *
 * 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
 * 注意：不允许改变队列元素的先后顺序 且不要求最高同学左右人数必须相等
 * 数据范围： 1≤n≤3000
 *
 * 思路：分别找到每个同学的左边最长递增子序列，右边最长递减子序列
 */
public class HJ24_dp最长递增or递减子序列 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] stu=new int[n];
        int[] left=new int[n];
        int[] right=new int[n];
        for (int i = 0; i < n; i++) {
            stu[i]=sc.nextInt();
        }
        //左边最长递增子序列
        for (int i = 0; i < n; i++){
            for (int j = 0; j < i; j++) {
                if (stu[i]>stu[j])
                    left[i]=Math.max(left[i],left[j]+1);
            }
        }
        //右边最长递减子序列
        for (int i = n-1; i >=0; i--){
            for (int j = n-1; j >i; j--) {
                if (stu[i]>stu[j])
                    right[i]=Math.max(right[i],right[j]+1);
            }
        }
        int max=0;
        for (int i = 0; i < n; i++) {
            if(right[i]+left[i]>max)
                max=right[i]+left[i];
        }
        System.out.println(n-max-1);
    }
}