合唱队__牛客网

Java

牛客281381469号

两个最长递增/减子序列问题,dp1[i]含义为0 ~ i中最长递增子序列长度。dp2[i]为i ~n - 1中最长递减子序列长度。
两层for循环，①求dp1[i],初始化dp1[0 ~ n - 1] = 1,因为最长递增子序列至少为其本身，i从1 ~ n - 1，j从0 ~ i，若nums[i] > nums[j]，dp1[i] = Math.max(dp1[i], dp[j] + 1。
②求dp2[i]，初始化dp2[0 ~ n - 1] = 1,因为最长递减子序列至少为其本身，i从n - 1 ~ 1，j从i ~ n - 1，若nums[i] > nums[j]，dp2[i] = Math.max(dp2[i], dp[j] + 1.
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        int[] dp1 = new int[n];
        int[] dp2 = new int[n];
        Arrays.fill(dp1, 1);
        Arrays.fill(dp2, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp1[i] = Math.max(dp1[i], dp1[j] + 1);
                }
            }

        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j]) {
                    dp2[i] = Math.max(dp2[i], dp2[j] + 1);
                }
            }
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(dp1[i] + dp2[i] - 1, max);
        }

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

发表于 2025-07-27 14:03:04 回复(0)

Java

向大佬致敬

import java.util.Scanner;
import java.math.*;
// 注意类名必须为 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 n = in.nextInt();
            int[] hight = new int[n];
            int[] left = new int[n];
            int[] right = new int[n];
            for (int i = 0; i < n; i++) {
                hight[i] = in.nextInt();
                left[i] = 1;
                right[i] = 1;
            }
            int temp = 0;
            for (int i = 0; i < hight.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (hight[i] > hight[j]) {
                        left[i] = Math.max(left[j] + 1, left[i]);
                    }
                }
            }
            for (int i =  hight.length - 1 ; i > 0; i--) {
                for (int j = hight.length - 1; j > i; j--) {
                    if (hight[i] > hight[j]) {
                        right[i] = Math.max(right[j] + 1, right[i]);
                    }
                }
            }
            for (int i = 0; i < n; i ++) {
                if (left[i] + right[i] - 1 > temp) {
                    temp = left[i] + right[i] - 1 ;
                }
            }
            System.out.println(n - temp);

        }
        in.close();
    }
}

最长递增序列，左右各做一次

发表于 2025-07-12 12:43:46 回复(0)

Java

牛客298721346号

最粗暴的方案当然是依次假定每一个值是队伍里的“山顶”，再各遍历一遍整个数组来检测这个“山顶”对应的出队人数。但这样做会引入许多重复的计算，不甚理想。

不妨用动态规划思路，考虑“终结于下标i元素的严格递增子序列最大长度”和“由下标i元素开始的严格递减子序列最大长度”。两者作和再减去一（下标i元素被多算了一次）就可以得到最大的队伍长度了。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            arr[i]=in.nextInt();
        }

        int[] mal = maxAscendingLength(arr);
        int[] mdl = maxDescendingLength(arr);
        int[] total = new int[len];
        
        for (int i = 0; i < len; i++) {
            total[i] = mal[i] + mdl[i] - 1;
        }

        int maxQueueSize = total[1];
        for (int i = 1; i < len - 1; i++) {
            if (maxQueueSize < total[i]) maxQueueSize = total[i];
        }

        System.out.println(len - maxQueueSize);
    }

    private static int[] maxAscendingLength(int[] arr) {
        int len = arr.length;
        int[] counts = new int[len];
        counts[0] = 1;
        int maxCurrCount, minCurrVal;
        for (int i = 1; i < len; i++) {
            maxCurrCount = counts[0];
            minCurrVal = arr[0];
            for (int j = 0; j < i; j++) {
                if (arr[j] <= minCurrVal) minCurrVal = arr[j];
                if (arr[j] < arr[i] && counts[j] > maxCurrCount) maxCurrCount = counts[j];
            }
            counts[i] = minCurrVal >= arr[i] ? 1 : maxCurrCount + 1;
        }
        return counts;
    }

    private static int[] maxDescendingLength(int[] arr) {
        int len = arr.length;
        int[] counts = new int[len];
        counts[len - 1] = 1;
        int maxCurrCount, minCurrVal;

        for (int i = len - 2; i > -1; i--) {
            maxCurrCount = counts[len - 1];
            minCurrVal = arr[len - 1];
            for (int j = len - 1; j > i; j--) {
                if (arr[j] <= minCurrVal) minCurrVal = arr[j];
                if (arr[j] < arr[i] && counts[j] > maxCurrCount) maxCurrCount = counts[j];
            }
            counts[i] = minCurrVal >= arr[i] ? 1 : maxCurrCount + 1;
        }
        return counts;
    }
}

发表于 2025-05-19 21:31:33 回复(0)

Java

牛客201673936号

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int N = in.nextInt();
            int[] T = new int[N];
            int[] left = new int[N];//记录从左往右的最长子序列数据
            int[] right = new int[N];//记录从右往左的最长子序列数据
            for (int i = 0; i < N; i++) {
                T[i] = in.nextInt();
            }

            //遍历找出左右最长序列数据,
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < i; j++) {
                    int m = N-1-i;
                    int n = N-1-j;
                    if(left[j] == 0){
                        left[j] = 1;
                    }
                    if(right[n] == 0){
                        right[n] = 1;
                    }
                    if(T[i]>T[j]){
                        left[i] = Math.max(left[i],left[j]+1);
                    }
                    if(T[m]>T[n]){
                        right[m] = Math.max(right[m],right[n]+1);
                    }
                }
            }
            int max = 0;
            //把每一个点作为最后一个请出同学，遍历比较得出最多剩下的同学
            for (int i = 0; i < N; i++){
                if(max < left[i]+right[i]-1){
                    //两者相加，减去重复计算的1，即为将此数放中间组成合唱队所需要的人数，取最大值max
                    max = left[i]+right[i]-1;
                }
            }
            System.out.println(N-max);
        }
    }
}

发表于 2024-09-06 13:00:19 回复(0)

Java

sinjiang

常见的最长上升子序列问题
思路： 1、查找每一个数的左边的最大递增子字符串长度，放入数组dp1中。 2、查找每个数的右边最大递增子字符串长度，放入数组dp2中 3、两者相加，减去重复计算的1，即为将此数放中间组成合唱队所需要的人数，取最大值max 4、总人数减去第三步所得，就可以得出需要出列的最少人数注意：身高是递增的，不能等于

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int N = in.nextInt();
            int[] T = new int[N];
            int[] left = new int[N];//记录从左往右的最长子序列数据
            int[] right = new int[N];//记录从右往左的最长子序列数据
            for (int i = 0; i < N; i++) {
                T[i] = in.nextInt();
            }

            //先从左往右找出最长子序列
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < i; j++) {
                    if(T[i]>T[j]){
                        left[i] = Math.max(left[i],left[j]);
                    }
                }
                left[i] = left[i]+1;
            }
            //再从右往左找出最长子序列
            for (int i = N-1; i >= 0; i--) {
                for (int j = N-1; j > i; j--) {
                    if(T[i]>T[j]){
                        right[i] = Math.max(right[i],right[j]);
                    }
                }
                right[i] = right[i] +1;
            }
            int max = 0;
            //把每一个点作为最后一个请出同学，遍历比较得出最多剩下的同学
            for (int i = 0; i < N; i++){
                if(max < left[i]+right[i]-1){
                    //两者相加，减去重复计算的1，即为将此数放中间组成合唱队所需要的人数，取最大值max
                    max = left[i]+right[i]-1;
                }
            }
            System.out.println(N-max);
        }
    }
}

发表于 2024-06-01 03:36:09 回复(0)

Java

早睡亿点

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);

}

}

编辑于 2024-04-07 16:13:19 回复(0)

Java

//201910101754657

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);
    }
}

编辑于 2024-03-17 23:53:58 回复(0)

Java

axby

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

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;
    }
}

编辑于 2024-03-15 17:58:41 回复(0)

Java

牛客214364484号

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();
    }
}

发表于 2024-01-23 18:00:18 回复(0)

Java

今生能进大厂吗

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

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);
        }
    }
}

编辑于 2023-12-11 18:15:34 回复(0)

Java

不要香菜的潜伏者很想和你交朋友

这个答案错了，正确答案是112

发表于 2023-10-24 14:12:27 回复(1)

Java

在泡池子的小饼干很想被叫靓仔

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();
        ;
    }
}

发表于 2023-07-03 19:47:59 回复(0)

Java

breeze_freedom

题目

有大佬知道这个是怎么错的吗，数据量小的测试案例能通过

package com.xlr.nowcoder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * 该题型是一个典型的动态规划+贪心
 * @see <a href="https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4?tpId=37&tqId=21247&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=">HJ24 合唱队</a>
 */
public class HJ24 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            int N=scanner.nextInt();
            ArrayList<Integer> list=new ArrayList<>();
            while (N-->0) list.add(scanner.nextInt());
            List<Integer> order =getIncrease(list);//顺着寻找最长递增子序列
            Collections.reverse(list);//将数组逆序
            List<Integer> reversed=getIncrease(list);//寻找逆序的最长递增子序列
            Collections.reverse(reversed);
            int max=-1;
            for(int index=0;index<order.size();index++){//找到顺序和逆序子序列之和，
                max=Math.max(max,order.get(index)+reversed.get(index));
            }
            System.out.println(list.size()-max+1);//因为当前元素多算了一遍故减去1个
        }
    }
    //计算最短增序列
    public static List<Integer> getIncrease(List<Integer> list){
        List<Integer > cnt=new ArrayList<>();//记录每个元素位置的最长递增子序列
        //计算每个元素的最长子串
        for(int index=0;index<list.size();index++){
            if(index<=0){//当前为第一个数字，直接加入最长递增子序列长度为1
                cnt.add(1);
            }else{
                int n=index;
                while (--n>=0){
                    if(list.get(n)<list.get(index)){//寻找前面最后一个比当前元素小的元素
                        break;
                    }
                }
                if(n>=0){//当n>=0存在时，找前面最后一个比当前元素小的元素,将该元素的最长递增子序列和当前元素组合并与上个元素比较最长的便是当前元素最长递增子序列
                    cnt.add(Math.max(cnt.get(index-1),cnt.get(n)+1));
                }else{
                    cnt.add(cnt.get(cnt.size()-1));//前面没有比当前元素小的元素，当前元素最长递增子序列就是上个元素的最长递增子序列
                }
            }
        }
        return cnt;
    }
}

发表于 2023-06-10 22:00:52 回复(1)

Java

牛客781396821号

动态规划，思路是找出每个人的左右侧各能有多少人，取左右侧之和最大的值

规律是左侧人数为之前所有身高比当前身高低的人中左侧人数最大的数值+1；右侧也是一样

注意陷阱（可能没有题目中的陷阱）：左右两侧任何一侧为1的数值不能使用，因为他不满足两侧都有比他低

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 n = in.nextInt();
            int[] tall = new int[n];
            int[] left = new int[n];
            int[] right = new int[n];
            tall[0] = in.nextInt();
            left[0] = 1;
            right[n - 1] = 1;

            // 计算每个人的左侧加上自己能有多少人
            for (int i = 1 ; i < n ; i++) {
                tall[i] = in.nextInt();
                left[i] = 1;
                for (int j = i - 1 ; j >= 0 ; j--) {
                    if (tall[i] > tall[j]) {
                        left[i] = left[i] > (left[j] + 1) ? left[i] : left[j] + 1;
                    }
                }
            }

            // 计算每个人的右侧加上自己能有多少人
            for (int i = n - 2 ; i >= 0 ; i--) {
                right[i] = 1;
                for (int j = i + 1 ; j < n ; j++) {
                    if (tall[i] > tall[j]) {
                        right[i] = right[i] > (right[j] + 1) ? right[i] : right[j] + 1;
                    }
                }
            }

            // 找出左右侧之和的最大值
            int sum = left[0] + right[0];
            for (int i = 1 ; i < n ; i++) {
                if (left[i] == 1 || right[i] == 1) {
                    continue;
                }
                int sum1 = left[i] + right[i];
                sum = sum < sum1 ? sum1 : sum;
            }
            System.out.println(n - sum + 1);
        }
    }
}

发表于 2023-05-11 10:23:37 回复(0)

Java

303300589

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;
        }
    }
}

发表于 2023-04-02 19:36:44 回复(0)

Java

璃吻

思路：以示例为准

186 186 150 200 160 130 197 200

左右

0：1->186 3->186 150/160 130

1：1->186 3->186 150/160 130

2：1->150 2->150 130

3：2->186/150 200 3->200 160 130

4：2->150 160 2->160 130

5：1->130 1->130

6：3->150 160 197 1->197

7：4->150 160 197 200 1->200

先遍历数组获得左排序个数，再获得右排序个数，左+右-1即为合唱队人数，取最大值

0：3->186 150/160 130

1：3->186 150/160 130

2：2->150 130

3：4->186/150 200 160 130

4：3->150 160 130

5：1->130

6：3->150 160 197

7：4->150 160 197 200

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            //left，遍历从左到i的升序个数
            int[] left = new int[n];
            for (int i = 0; i < n; i++) {
                left[i] = 1;//最起码当前数为1
                for (int j = 0; j < i; j++) {
                    if (a[j] < a[i]) {
                        //每有一个比a[i]小的数，在left[j]的基础上加1和left[i]比大小，保证是升序数
                        left[i] = Math.max(left[j] + 1, left[i]);
                    }
                }
            }
            //right，遍历从右到i的升序个数
            int[] right = new int[n];
            for (int i = n - 1; i >= 0; i--) {
                right[i] = 1;
                for (int j = n - 1; j > i; j--) {
                    if (a[j] < a[i]) {
                        right[i] = Math.max(right[j] + 1, right[i]);
                    }
                }
            }
            int people = 1;//1<=n<=3000，所以最少为合唱队最少1个人
            for (int i = 0; i < n; i++) {
                //以当前数为中心，左右升序数相加减一即是合唱队,重合了最高的人所以减一
                //直接使用a[i]数组，创建新数组浪费空间
                a[i] = left[i] + right[i] - 1;
                people = Math.max(people, a[i]); //取合唱队最大值
            }
            System.out.println(n - people); //总人数减去最大合唱队人数就是要出列的同学人数
        }

    }
}

发表于 2023-03-03 20:09:40 回复(0)

Java

董乃士

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;
    }
}

发表于 2023-02-27 14:25:18 回复(0)

合唱队

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题