Longest alternating subarray after removing at most one element

impl Solution {
  pub fn longest_alternating(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    if n <= 2 {
      if n == 2 && nums[0] != nums[1] {
        return 2;
      }
      return 1;
    }

    // For each position, compute the sign of comparison with next element
    // sign[i] = sign of nums[i+1] - nums[i]: 1, -1, or 0
    let sign: Vec<i32> = (0..n-1).map(|i| {
      if nums[i+1] > nums[i] { 1 }
      else if nums[i+1] < nums[i] { -1 }
      else { 0 }
    }).collect();

    // Without removal: find longest alternating subarray
    // fwd[i] = length of longest alternating subarray ending at index i
    // bwd[i] = length of longest alternating subarray starting at index i
    let mut fwd = vec![1i32; n];
    for i in 1..n {
      if sign[i-1] != 0 && (i < 2 || sign[i-1] != sign[i-2]) {
        // Actually fwd[i]: alternating subarray ending at i
        // We extend if sign[i-1] != 0 and sign[i-1] != sign[i-2] (alternation)
        if fwd[i-1] == 1 {
          // Previous was length 1, just need sign[i-1] != 0
          if sign[i-1] != 0 {
            fwd[i] = 2;
          }
        } else {
          // fwd[i-1] >= 2, sign[i-2] exists and != 0
          if sign[i-1] != 0 && sign[i-1] != sign[i-2] {
            fwd[i] = fwd[i-1] + 1;
          } else if sign[i-1] != 0 {
            fwd[i] = 2;
          }
        }
      } else if sign[i-1] != 0 {
        fwd[i] = 2;
      }
    }

    let mut bwd = vec![1i32; n];
    for i in (0..n-1).rev() {
      if sign[i] != 0 {
        if bwd[i+1] == 1 {
          bwd[i] = 2;
        } else {
          // bwd[i+1] >= 2, sign[i+1] exists (since i+1 < n-1 because bwd[i+1]>=2)
          if i + 1 < n - 1 && sign[i] != sign[i+1] {
            bwd[i] = bwd[i+1] + 1;
          } else {
            bwd[i] = 2;
          }
        }
      }
    }

    let mut ans = *fwd.iter().max().unwrap();

    // Try removing each element i (1..n-2), connecting fwd[i-1] and bwd[i+1]
    for i in 1..n-1 {
      // After removing element i, elements i-1 and i+1 become adjacent.
      // We need to check if they can form an alternating continuation.
      // The sign between i-1 and i+1 in the new array:
      let new_sign = if nums[i+1] > nums[i-1] { 1 }
              else if nums[i+1] < nums[i-1] { -1 }
              else { 0 };

      if new_sign == 0 { continue; }

      // fwd[i-1]: alternating subarray ending at i-1
      // The last sign in fwd[i-1]'s subarray is sign[i-2] (if fwd[i-1] >= 2)
      // We need new_sign to alternate with that last sign.

      let left_len;
      if fwd[i-1] >= 2 {
        // Last sign in fwd ending at i-1 is sign[i-2]
        if sign[i-2] != new_sign {
          left_len = fwd[i-1];
        } else {
          left_len = 1;
        }
      } else {
        left_len = 1; // just element i-1 alone
      }

      let right_len;
      if bwd[i+1] >= 2 {
        // First sign in bwd starting at i+1 is sign[i+1]
        if i + 1 < n - 1 && sign[i+1] != new_sign {
          right_len = bwd[i+1];
        } else {
          right_len = 1;
        }
      } else {
        right_len = 1;
      }

      // Total = left_len + right_len (no double counting, the connection is implicit).
      ans = ans.max(left_len + right_len);
    }

    // Also try removing first or last element
    // Removing first: answer is at least bwd[1]
    // Removing last: answer is at least fwd[n-2]
    // These are already covered by the no-removal case since bwd[1] and fwd[n-2] are subarrays of original.

    ans
  }
}