题解 | 小红的区间删除

// 小红拿到了一个数组，她准备进行最多一次以下操作：
// 选择两个相等的元素，将这两个元素之间的所有元素删除。
// 小红想知道，她最多可以删除多少个元素？

// 1≤n≤200000
// 1≤ai≤10**9

// 相同元素的最大距离，遍历超时
// 记录每个元素的第一次下标和最后一次下标，计算最大差距
// 在读取数据的同时完成比较
// 通过哈希表来查找与存储, 哈希取mod 199999
// 我赌它不会有两个不同的元素哈希值一样

// 遍历dif，输出最大值。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct tmp
{
   int first;
};


int main() {
   int len;
   struct tmp arr[199999];
   int i;
   int max = 0;
   int dif = 0;
   int income = 0;

   // 获取数据
   scanf("%d", &len);
   memset(arr, 0, sizeof(struct tmp) * 199999);

   for (i = 1; i <= len; i++)
   {
      scanf("%d", &income);
      if (arr[income % 199999].first == 0)
      {
         arr[income % 199999].first = i;
      }
      else
      {
         dif = i - arr[income % 199999].first - 1;
         max = (max>dif)?max:dif;
      }
   }

   
   printf("%d", max);
   return 0;
}