首页 > 试题广场 >

排序子序列

[编程题]排序子序列

热度指数：14516 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.
如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2

输入描述:

输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)

第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。

输出描述:

输出一个整数表示牛牛可以将A最少划分为多少段排序子序列

示例1

输入

6
1 2 3 2 2 1

输出

算法知识视频讲解

Java

牛客581130865号

//Java动态规划做法

//定义状态：F[i]为截止到num[i]能分为的组数
//状态转移：F[i] = F[i - 1] + (state.equals(newState) ? 0 : 1)
//初始状态：F[0] = 1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = 0;
        int[] num = null;

        while (scan.hasNextInt()){
            n = scan.nextInt();
            num = new int[n];

            for (int i = 0; i < n; i++) {
                num[i] = scan.nextInt();
            }

            System.out.println(countGroup(num));
        }
    }

    //返回数组num能分成的组数
    public static int countGroup(int[] num){
        //如果数组为空，则分的组数为0
        if(num == null){
            return 0;
        }

        //如果数组的长度小于等于2，那么分的组数为1
        int length = num.length;
        if(length <= 2){
            return  1;
        }

        //定义状态：F[i]为截止到num[i]能分为的组数
        //状态转移：F[i] = F[i - 1] + (state.equals(newState) ? 0 : 1)
        //初始状态：F[0] = 1
        int[] F = new int[length];
        String state = null;        //表示当前子序列的顺序状态，空代表当前子序列的状态未知，up代表升序，down代表降序。
        F[0] = 1;

        //递推每个状态
        for (int i = 1; i < length; i++) {
            String newState = null;

            if(num[i - 1] < num[i]){
                newState = "up";
            } else if (num[i - 1] > num[i]) {
                newState = "down";
            }

            //当newState为空时说明当前num[i - 1]与num[i]状态为相同，此时状态不变，F[i] = F[i - 1]
            if(newState != null){
                //当state为空时说明num[i - 1]之前的序列的状态未知或者之前的序列是相同的，此时状态不变，不必划分新组，F[i] = F[i - 1]
                if(state == null){
                    state = newState;
                    F[i] = F[i - 1];
                }else {
                    //到这里state与newState都不为空，如果两个状态相同则不必划分新组，F[i] = F[i - 1]
                    //如果状态不同，则需要划分新的组，F[i] = F[i - 1] + 1
                    if(!state.equals(newState)) {
                        F[i] = F[i - 1] + 1;
                        state = null;   //由于当前并不知道划分的新组到底是升序还是降序还是不增不降的序列，也就是状态未知，所以这里把状态置为空
                    }else {
                        F[i] = F[i - 1];
                    }
                }
            }else {
                F[i] = F[i -1];
            }
        }
        
        //返回截止到num[length - 1]，num数组能分的组数
        return F[length - 1];   
    }
}

发表于 2023-03-28 22:54:56 回复(0)

Java

doi灬

import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int[] ints = new int[scanner.nextInt()+1];//防止最后一个数是单独的一组数组长度多给一个最后让它和0比较
while(scanner.hasNext()){
for (int i = 0 ; i<ints.length-1 ; i++){ //因为数组长度多给了一个所以要i<ints.length-1
ints[i] = scanner.nextInt();
}

}

int sum = 0;

int i = 1;

//每次当 ints[i-1] 与 ints[i] 的关系发生改变的时候sum++

while(i < ints.length) {
if (ints[i-1] < ints[i]){
while (i < ints.length && ints[i-1] < ints[i] ){
i++;
}
sum++;
i++;
}else if (ints[i-1] == ints[i]){
i++;
}else {
while (i < ints.length && ints[i-1] > ints[i] ){
i++;
}
sum++;
i++;
}
}
System.out.println(sum);
}
}

发表于 2021-05-25 14:09:49 回复(0)

Java

牛客298457298号

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[] a = new int[n];
        for (int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        System.out.println(sortList(a));
    }
    public static int sortList(int[] a){
        int count = 1;
        int flag = 0;
        for (int i = 1;i<a.length;i++){
            if (a[i-1] > a[i]) {
                if (flag == 1 || flag == 0){
                    flag = 1;
                }else if (flag == -1){
                    flag = 0;
                    count++;
                }
            }else if (a[i-1] < a[i]) {
                if (flag == -1 || flag == 0){
                    flag = -1;
                }else if (flag == 1){
                    flag = 0;
                    count++;
                }
            }else if (a[i-1] == a[i]) {
            }
        }
        return count;
    }
}

编辑于 2021-04-14 23:15:37 回复(0)