首页 > 试题广场 >

交错序列

[编程题]交错序列

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

我们定义一个由数字 0 和 1 组成的序列是交错序列，当且仅当在这个序列中 0 和 1 是轮流出现的，比如，0，010，10101 都是交错序列。

现在给出了一个由数字 0 和 1 组成的序列𝐴，它可能不是一个交错序列，但是你可以从这个序列中选择一些数字出来，按他们在序列𝐴中原有的相对顺序排列(即选取𝐴的一个子序列)，使得你最后得到的是一个交错序列。问这样能得到的交错序列的最长长度是多少。

数据范围： $1 \le n \le 10^5 \$ ，序列中只包含 0 和 1。

输入描述:

第一行包含一个整数𝑛，表示输入序列的长度。
第二行包含 𝑛 个 0 或 1，表示对应的序列。

输出描述:

输出能够得到的最长交错序列的长度。

示例1

输入

3
0 1 0

输出

示例2

输入

8
1 1 0 0 1 1 0 0

输出

算法知识视频讲解

Javascript_V8

biub_

let n=readline()
let input=readline()
function solve(n, input) {
    let arr = input.split(' ').map(Number)
    let pre = arr[0]
    let cnt = 1
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] != pre) {
            cnt++
            pre = arr[i]
        }
    }
    console.log(cnt)
}
solve(n, input)

但最开始自己陷入了自己挖的坑，想着递归去了。

// 没通过 超了，但就是想留着
let n = '3'
let input = "1 1 0 0 1 1 0 0"
function solve(n, input) {
    let arr = input.split(' ').map(Number)
    if (arr.length > 1) {
        let ans = recursion(arr, arr[0])
        console.log(ans)
    }else{
        console.log(0)
    }

}
function recursion(arr, num) {
    if (arr.indexOf(num) === -1) {
        return 0
    } else {
        let index = arr.indexOf(1 - num)
        arr = arr.slice(index)
        return 1 + recursion(arr, 1 - num)

    }
}
solve(n, input)

发表于 2022-01-18 08:55:00 回复(0)