具有开关元件的最长子阵列

Question

如果奇数和偶数元素相等，则数组称为“切换”。

例子：

[2,4,2,4]是一个切换数组，因为偶数位置（索引 0 和 2）和奇数位置（索引 1 和 3）的成员相等。

如果A = [3,7,3,7, 2, 1, 2]，则切换子阵列为：

== > [3,7,3,7]和[2,1,2]

因此，最长的切换子阵列是[3,7,3,7]，长度为 4。

再举一个例子，如果A = [1,5,6,0,1,0]，唯一的切换子阵列是[0,1,0]。

又如：A= [7,-5,-5,-5,7,-1,7]，切换子数组为[7,-1,7]和[-5,-5,-5] .

题：

编写一个接收数组并找到其最长切换子数组的函数。

我想知道您是如何解决这个问题的，以及您使用哪些策略来以良好的时间复杂度解决这个问题？

Answer 1

我假设数组是零索引的。

if arr.size <= 2
    return arr.size
else 
   ans = 2
   temp_ans = 2 // We will update ans when temp_ans > ans;
   for i = 2; i < arr.size ; ++i
       if arr[i] = arr[i-2]
            temp_ans = temp_ans + 1;
       else
            temp_ans = 2;
       ans = max(temp_ans , ans);
   return ans;

我认为这应该有效，我认为不需要任何解释。
示例代码

Answer 2

 private static int solve(int[] arr){
        if(arr.length == 1) return 1;
        int even = arr[0],odd = arr[1];
        int start = 0,max_len = 0;
        for(int i=2;i<arr.length;++i){
            if(i%2 == 0 && arr[i] != even || i%2 == 1 && arr[i] != odd){
                 max_len = Math.max(max_len,i - start);
                 start = i-1;
                 if(i%2 == 0){
                     even = arr[i];
                     odd = arr[i-1];
                 }else{
                     even = arr[i-1];
                     odd = arr[i];
                 }
            }
        }     


        return Math.max(max_len,arr.length - start);
    }

• 这就像一个滑动窗口问题。
• 我们用 2 个变量even和跟踪偶数和奇数相等odd。
• 每当我们遇到未满足的条件时，例如索引偶数但不等于even变量，同样适用于odd，我们首先
  • 记录到目前为止的长度max_len。
  • 重置start到i-1，因为这是需要柜面的所有元素相等。
  • 复位even并odd根据当前索引i到arr[i]和arr[i-1]分别。

演示： https : //ideone.com/iUQti7