解题思路

这是一个序列处理问题。具体要求：

  1. 给定一个数字序列
  2. 需要找出最长的交错子序列（相邻元素不相同）
  3. 输出最长交错子序列的长度

解决方案：

  1. 遍历序列，统计相邻元素不同的次数
  2. 初始长度为1（包含第一个元素）
  3. 每当遇到与前一个元素不同的数字时，长度加1
  4. 最终输出统计的长度

代码

#include <iostream>
using namespace std;

const int MAXN = 100005;

int main() {
    int n;
    int arr[MAXN];
    
    // 读入序列长度和序列
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // 计算最长交错序列
    int result = 1;  // 初始长度为1
    for(int i = 1; i < n; i++) {
        if(arr[i-1] != arr[i]) {
            result++;  // 找到一个不同的元素
        }
    }
    
    printf("%d\n", result);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读入序列长度
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        // 读入序列
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 计算最长交错序列
        int result = 1;  // 初始长度为1
        for(int i = 1; i < n; i++) {
            if(arr[i-1] != arr[i]) {
                result++;  // 找到一个不同的元素
            }
        }
        
        System.out.println(result);
    }
}

def solve():
    # 读入序列长度和序列
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 计算最长交错序列
    result = 1  # 初始长度为1
    for i in range(1, n):
        if arr[i-1] != arr[i]:
            result += 1  # 找到一个不同的元素
    
    print(result)

if __name__ == "__main__":
    solve()

算法及复杂度

  • 算法：线性扫描
  • 时间复杂度： - 只需要遍历一次序列
  • 空间复杂度： - 需要存储输入序列