数组中两个不同元素之间的最大距离

我有一个问题,我需要找到一个数组中两个不同元素之间的最大距离.

例如:给定一个数组4,6,2,2,6,6,4,该方法应返回5最大距离.

我能够使用两个for循环来解决问题,但它不是一个优化的解决方案.我试图通过在单个for循环中进行优化来优化它.

这是我目前的解决方案:

int [] A = {4,6,2,2,6,6,4};
int N = A.length;
int result = 0;

for (int i = 0; i 

如何在时间复杂度方面做得更好？


1> Dmitry Byche..：
简单(非嵌套)循环就足够了,但应考虑两种情况:最好的结果是

  4,6,2,2,6,6,4
    ^         ^ - moving first


要么

  4,6,2,2,6,6,4
  ^         ^   - moving last


例如:[4, 2, 4, 4, 4] 移动第一个带来答案,如果在[4, 4, 4, 2, 4] 最后移动的情况下应该使用.

  int first = 0;
  int last = A.length - 1;

  // 1st case: moving "first"
  while (first  diff2
    ? diff1
    : diff2;


所以我们有O(N)时间复杂性.

编辑:让我们证明至少有一个索引是0或者length - 1.让我们通过矛盾来做.假设我们有一个类似的解决方案

  a, b, c, .... d, e, f, g
        ^ ..... ^  <- solution indexes (no borders)


c必须是左边的项目d,否则我们可以采取a或b索引并有一个改进的解决方案.d必须是右边的项目,c或者我们可以再次将最后一个索引向右推,并有一个更好的解决方案.所以我们有

  d, d, c .... d, c, c, c
        ^ .... ^  <- solution indexes 


现在,因为d <> c(c..d是一个解决方案),我们可以改进解决方案

  d, d, c .... d, c, c, c
        ^ .... ^           <- solution indexes 
  ^       ....          ^  <- better solution


我们有一个矛盾(所谓的解决方案不是一个 - 我们有更好的选择),这就是为什么至少有一个索引必须是0或length - 1.

现在我们有两个测试场景:

  a, b, ..... y, z
     ^  ......   ^ <- moving first
  ^  ......   ^    <- moving last


我们可以将两个条件组合成if一个循环:

  int result = 0;

  for (int i = 0; i