最长递增子数组：从两个数组中构造非递减序列的最大连续长度-java教程-PHP中文网

最长递增子数组：从两个数组中构造非递减序列的最大连续长度

给定两个等长数组 a 和 b，需选取相同起止索引的连续子段 [i..j]，对每个位置 k ∈ [i,j]，可任选 a[k] 或 b[k] 构成新数组 c；要求 c 非递减，目标是最大化子段长度 j−i+1。

给定两个等长数组 a 和 b，需选取相同起止索引的连续子段 [i..j]，对每个位置 k ∈ [i,j]，可任选 a[k] 或 b[k] 构成新数组 c；要求 c 非递减，目标是最大化子段长度 j−i+1。

本题本质是带状态转移的动态规划问题：对每个位置 i，我们关心以 A[i] 或 B[i] 结尾的、能构成非递减序列的最长连续子数组长度。关键观察在于——由于必须选取连续下标（即子数组必须是原数组中一段连续区间），且在每个位置 k 只能选 A[k] 或 B[k]，因此状态只需记录「以 A[i] 结尾」和「以 B[i] 结尾」的最长合法长度即可。

定义两个状态变量：

alen：以 A[i] 作为第 i 位元素时，能构成的最长非递减连续子数组长度；
blen：以 B[i] 作为第 i 位元素时，能构成的最长非递减连续子数组长度。

状态转移逻辑如下（从左到右遍历，i ≥ 1）：

若 A[i] ≥ A[i−1]，则可在以 A[i−1] 结尾的序列后接 A[i]，长度为 alen_prev + 1；
若 A[i] ≥ B[i−1]，则可在以 B[i−1] 结尾的序列后接 A[i]，长度为 blen_prev + 1；
同理，B[i] 可接在 A[i−1] 或 B[i−1] 之后（只要满足 ≥ 条件）；
因此，a = max( (A[i]≥A[i−1] ? alen+1 : 0), (A[i]≥B[i−1] ? blen+1 : 0) )，但为避免初值干扰，统一初始化为 1（单元素总是合法），再按条件更新。

注意：每个位置至少可独立成长度为 1 的序列，故初始 alen = blen = 1（i=0 时），后续从 i=1 开始递推。

以下是完整、高效（时间复杂度 O(n)，空间复杂度 O(1)）的 Java 实现：

public int solve(int[] A, int[] B) {
    int n = A.length;
    if (n == 0) return 0;
    if (n == 1) return 1;

    int alen = 1, blen = 1; // 分别表示以 A[0]、B[0] 结尾的最长长度
    int result = 1;

    for (int i = 1; i = A[i-1]) a = Math.max(a, alen + 1);
        if (A[i] >= B[i-1]) a = Math.max(a, blen + 1);

        if (B[i] >= A[i-1]) b = Math.max(b, alen + 1);
        if (B[i] >= B[i-1]) b = Math.max(b, blen + 1);

        alen = a;
        blen = b;
        result = Math.max(result, Math.max(alen, blen));
    }

    return result;
}

✅ 正确性保障：该解法覆盖所有合法转移路径（每个位置仅依赖前一位置的两种状态），避免了贪心策略（如原始代码中重置 s=1 的盲目性）导致的局部最优陷阱。
⚠️ 注意事项：