Найти max j - i, где arr [j]! = Arr [i]

Question

для входного массива {1,3,2,9}, вывод равен 3 (arr [3]! = Arr [0])

для входного массива {1,3,2,9,1} вывод равен 3 (arr [3]! = Arr [0])

Я не мог придумать никакого полезного решения, чем n ^ 2 loop

import java.util.*;

class Solution {
    int getTheDiff(int[] A) {
        int N = A.length;
        int result = 0;
        for (int i = 0; i < N; i++)
            for (int j = i; j < N; j++)
                if (A[i] != A[j])
                    result = Math.max(result, j - i);
        return result;
    }
}

Этот код был заменен на

    int diff = 0;

    int i =0;
    int[] arr = {-1,-2,-3,-5,-73};


    for (int j = 1; j < arr.length; j++) {
        if(arr[j] != arr[i]) {
            diff = Math.max(diff,j-i);
        }
    }
    System.out.println(diff);

Но все равно не удается выполнить все контрольные примеры, не знаю, что пошло не так.

Answer 1

Основная идея : Ответ: разница между первым неповторяющимся значением с terminal value (по индексу 0 или A.length - 1) .

int getTheDiff(int[] A){
    int diff1=0, diff2=0;
    for(int i=0, j=A.length-1; i<j;i++){
        if(A[i]!=A[j])
            diff1 = Math.max(j-i, diff1);
    }
    for(int i=A.length-1, j=0; i>j;i--){
        if(A[i]!=A[j])
            diff2 = Math.max(j-i, diff2);
    }
    return Math.max(diff1, diff2);
}