Odd Even Subsequences
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Odd Even Subsequences * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Odd Even Subsequences * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given an array of integers A of size N. * Find the length of the longest subsequence of A that is "Odd-Even". * * Definition: * A subsequence is Odd-Even if the parities of the elements alternate. * There are two valid patterns: * 1. Odd, Even, Odd, Even... * 2. Even, Odd, Even, Odd... * * We need to find the maximum length possible satisfying either of these patterns. * * --------------------- * 2. Logical Breakdown & Greedy Strategy * --------------------- * Let parity(x) = x % 2. * We want to maximize the length of a chain where parity(x_i) != parity(x_{i+1}). * * Key Observation (Greedy Property): * To maximize the length, we should always pick the first available number that satisfies * the required parity for the current position in the chain. * * Why? * Suppose we need an Odd number. We encounter the first Odd number at index i. * If we skip A[i] to pick a later Odd number at index k (k > i), we strictly reduce * the remaining search space (the suffix starting at k+1 is smaller than the suffix at i+1). * Therefore, picking the earliest valid number is always optimal. * * Algorithm: * Since we don't know if the optimal sequence starts with Odd or Even, we calculate both: * * Process 1 (Force Start Odd): * - Search for first Odd. Then search for first Even after that. Then Odd... * - Count the length. * * Process 2 (Force Start Even): * - Search for first Even. Then search for first Odd after that. Then Even... * - Count the length. * * Result = max(Length_Odd_Start, Length_Even_Start). * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= N <= 100,000 * 1 <= A[i] <= 10^9 * * Time Complexity: * O(N) - We iterate through the array at most twice (or once with state tracking). * * Space Complexity: * O(1) - We only need integer counters. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - Integer Array A. * * Output: * - Integer denoting the maximum length. * * --------------------- * 5. Examples * --------------------- * Input 1: A = [1, 2, 2, 5, 6] * - Start Odd: [1 (odd), 2 (even), 5 (odd), 6 (even)] -> Length 4 * - Start Even: [2 (even), 5 (odd), 6 (even)] -> Length 3 * - Max: 4 * * Input 2: A = [2, 2, 2, 2, 2, 2] * - Start Odd: No odd numbers found -> Length 0 * - Start Even: [2] -> Next needs odd (none found) -> Length 1 * - Max: 1 * * ============================================================================================ */ public class OddEvenSubsequences { public int solve(int[] A) { // TODO: Implement solution return 0; } }