交替序列长度的最大值

1、题目描述

给出n个正整数，你可以随意从中挑选一些数字组成 一段序列S，该序列满足以下两个条件：
1.奇偶交替排列：例如："奇，偶，奇，偶，奇.…" 或者 "偶，奇，偶, 奇..."
2.前一个数必须严格小于下一数。
注意：挑选出来的数字可以任意排列组成S，不需要保持原本的相对顺序。
请你求出该序列S长度的最大值。

输入描述

输入的的第一行给出正整数n(1<= n<= 100)   代表数组的长度。
输入的第二行为n个正整数ai(1 <= ai<= 10^9)，用空格分隔。

输出描述

输出序列S长度的最大值。

示例 1 

输入：

10
6 6 1 1 5 3 2 6 8 10
输出：

4

实例2
 

输入：

10
4 8 6 8 6 6 2 10 2 10

输出：

1

2、解题思路

要解决这个问题，我们需要找到满足特定条件的最长子序列。具体来说，序列中的数字必须严格递增且奇偶交替排列。我们可以通过动态规划的方法来高效地解决这个问题。

1. 排序数组：首先将数组排序，这样我们可以方便地处理递增的条件。

2. 动态规划：使用动态规划来记录以每个数字结尾的最长满足条件的子序列长度。我们需要维护两个动态规划数组：

   • dp_odd[i] 表示以第i个数字结尾且该数字为奇数时的最长子序列长度。

   • dp_even[i] 表示以第i个数字结尾且该数字为偶数时的最长子序列长度。

3. 状态转移：对于每个数字，检查其奇偶性，并根据前一个数字的奇偶性来更新当前数字的动态规划值。具体来说：

   • 如果当前数字是奇数，它可以接在任意一个比它小的偶数后面，因此更新 dp_odd[i] 为 dp_even[j] + 1，其中 nums[j] < nums[i] 且 nums[j] 是偶数。

   • 同理，如果当前数字是偶数，它可以接在任意一个比它小的奇数后面，因此更新 dp_even[i] 为 dp_odd[j] + 1，其中 nums[j] < nums[i] 且 nums[j] 是奇数。

4. 结果提取：最终结果是 dp_odd 和 dp_even 数组中的最大值。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象用于读取输入
        Scanner scanner = new Scanner(System.in);
        
        // 读取数组的长度n
        int n = scanner.nextInt();
        
        // 创建数组nums用于存储输入的整数
        int[] nums = new int[n];
        
        // 读取n个整数并存入数组nums
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        
        // 对数组进行排序，以便后续处理递增条件
        Arrays.sort(nums);

        // 创建两个动态规划数组：
        // dpOdd[i]表示以nums[i]结尾且nums[i]为奇数的最长子序列长度
        // dpEven[i]表示以nums[i]结尾且nums[i]为偶数的最长子序列长度
        int[] dpOdd = new int[n];
        int[] dpEven = new int[n];
        
        // 初始化所有位置的最长子序列长度为1（至少包含自己）
        Arrays.fill(dpOdd, 1);
        Arrays.fill(dpEven, 1);

        // 用于记录最终结果，初始化为1（至少可以选一个数）
        int maxLen = 1;

        // 遍历数组中的每个数字
        for (int i = 0; i < n; i++) {
            // 检查当前数字是否为奇数
            if (nums[i] % 2 == 1) {
                // 如果是奇数，遍历前面的所有数字
                for (int j = 0; j < i; j++) {
                    // 如果前面的数字是偶数且比当前数字小
                    if (nums[j] < nums[i] && nums[j] % 2 == 0) {
                        // 更新dpOdd[i]为dpEven[j]+1和当前值的较大者
                        dpOdd[i] = Math.max(dpOdd[i], dpEven[j] + 1);
                    }
                }
                // 更新全局最大值
                maxLen = Math.max(maxLen, dpOdd[i]);
            } else {
                // 如果是偶数，遍历前面的所有数字
                for (int j = 0; j < i; j++) {
                    // 如果前面的数字是奇数且比当前数字小
                    if (nums[j] < nums[i] && nums[j] % 2 == 1) {
                        // 更新dpEven[i]为dpOdd[j]+1和当前值的较大者
                        dpEven[i] = Math.max(dpEven[i], dpOdd[j] + 1);
                    }
                }
                // 更新全局最大值
                maxLen = Math.max(maxLen, dpEven[i]);
            }
        }

        // 输出最长子序列的长度
        System.out.println(maxLen);
    }
}

代码解释

1. 输入处理：读取输入的数组长度 n 和数组 nums。

2. 排序数组：将数组 nums 排序以便处理递增条件。

3. 动态规划初始化：初始化两个动态规划数组 dpOdd 和 dpEven，分别记录以奇数和偶数结尾的最长子序列长度，初始值为1。

4. 动态规划填充：

   • 对于每个数字 nums[i]，根据其奇偶性，检查所有比它小的数字 nums[j]，并根据 nums[j] 的奇偶性更新 dpOdd[i] 或 dpEven[i]。

5. 结果提取：在填充动态规划数组的过程中，始终保持更新全局最大值 maxLen，最终输出该值。