交替序列长度的最大值
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、解题思路
要解决这个问题，我们需要找到满足特定条件的最长子序列。具体来说，序列中的数字必须严格递增且奇偶交替排列。我们可以通过动态规划的方法来高效地解决这个问题。
-
排序数组：首先将数组排序，这样我们可以方便地处理递增的条件。
-
动态规划：使用动态规划来记录以每个数字结尾的最长满足条件的子序列长度。我们需要维护两个动态规划数组：
-
dp_odd[i]表示以第i个数字结尾且该数字为奇数时的最长子序列长度。 -
dp_even[i]表示以第i个数字结尾且该数字为偶数时的最长子序列长度。
-
-
状态转移：对于每个数字，检查其奇偶性，并根据前一个数字的奇偶性来更新当前数字的动态规划值。具体来说：
-
如果当前数字是奇数，它可以接在任意一个比它小的偶数后面，因此更新
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]是奇数。
-
-
结果提取：最终结果是
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);// 读取数组的长度nint n = scanner.nextInt();// 创建数组nums用于存储输入的整数int[] nums = new int[n];// 读取n个整数并存入数组numsfor (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);}
}代码解释
-
输入处理：读取输入的数组长度
n和数组nums。 -
排序数组：将数组
nums排序以便处理递增条件。 -
动态规划初始化：初始化两个动态规划数组
dpOdd和dpEven，分别记录以奇数和偶数结尾的最长子序列长度，初始值为1。 -
动态规划填充：
-
对于每个数字
nums[i]，根据其奇偶性，检查所有比它小的数字nums[j]，并根据nums[j]的奇偶性更新dpOdd[i]或dpEven[i]。
-
-
结果提取：在填充动态规划数组的过程中，始终保持更新全局最大值
maxLen，最终输出该值。