首页 > 试题广场 >

交错序列

[编程题]交错序列

我们定义一个由数字 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

算法知识视频讲解

白伟仝

发表于 2020-06-27 16:16:54

import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.ne 展开全文

17c89

发表于 2024-02-02 11:53:46

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while 展开全文

bao_hu_yuan_zhang

发表于 2024-03-13 19:51:19

#include <iostream> #include <vector> using namespace std; int main() { int i=0; int n=0; cin>>n; vector <int&g 展开全文

灿烂ll人生

发表于 2022-06-06 08:52:44

动态规划，很容易可以想到关联方程，当相邻数值不等时dp[i]=dp[i-1]+1; 相等时则：dp[i]=dp[i-1]; #include<bits/stdc++.h> using namespace std; int main(){ 展开全文

bandiaoz

发表于 2024-12-29 02:17:06

解题思路这是一个序列处理问题。具体要求：给定一个数字序列需要找出最长的交错子序列（相邻元素不相同）输出最长交错子序列的长度解决方案：遍历序列，统计相邻元素不同的次数初始长度为1（包含第一个元素）每当遇到与前一个元素不同的数字时，长度加1 最终输出统计的长度代码 c++ 展开全文

字符串

难度：

29条回答 14收藏 6441浏览

查看代码