Сканирование массива для длины самой длинной субматрицы, делящейся на 3

Question

Я пишу программу, которая сканирует массив и производит длину самого длинного подматрица, содержащего элементы, сумма которых делится на 3. Я работал с использованием понятие из другого вопроса здесь, используя концепцию суммы префикса - сканирование первой и последней сумм, которые mododu 3 выдают 0,1, 2, вычисляя разницу между каждым набором и возвращая самую большую из трех.

Я решил протестировать его с помощью генератора случайных массивов. 90% времени он работает, но в других он пропускает правильный ответ несколькими номерами. Любая идея, что не так?

Я включил тестер, который включает в себя неэффективный метод, который делает то же самое. Изображение включено:

Выход:

84 | 4 | 94 | 27 | 85 | 10 | 87 | 11 | 66 | 34 | 66 | 42 | 26 | 65 | 12 | 93 | 14 |

размер массива: 17

Bad Что: 15

Мои Что: 13

Код:

import static java.lang.Math.*; 
import java.util.Random; 

public class Q1 { 
    public static void main(String args[]) { 
     Random rand = new Random(); 
     int[] a = new int[rand.nextInt(100)]; 
     for (int i = 0; i < a.length; i++) 
     { 
      a[i] = rand.nextInt(100); 
      System.out.print(a[i] + "|"); 
     } 
     System.out.println(); 
     System.out.println("array size is: " + a.length); 
     System.out.println("Bad What: " + badWhat(a)); 
     System.out.println("My What: " + what(a)); 
    } 

    public static int what(int[] a) { 
     int sumLeft = 0, sumRight = 0; 
     int zero, one, two; 
     int firstZero = 0, firstOne = 0, firstTwo = 0, lastZero = 0, lastOne = 0, lastTwo = 0; 
     for (int i = 0; i < a.length; i++) { 
      sumLeft += negMod(a[i])%3; 
      sumRight += negMod(a[a.length - 1 - i]%3); 
      if ((sumLeft) % 3 == 0) 
       firstZero = i; 
       if ((sumRight) % 3 == 0) 
        lastZero = i; 
       if ((sumLeft) % 3 == 1) 
        firstOne = i; 
       if ((sumRight) % 3 == 1) 
        lastOne = i; 
       if ((sumLeft) % 3 == 2) 
        firstTwo = i; 
       if ((sumRight) % 3 == 2) 
        lastTwo = i; 
      } 
     firstOne++; 
     firstTwo++; 
     zero = lastZero - firstZero + 1; 
     one = lastOne - firstOne; 
     two = lastTwo - firstTwo; 
     int result = max(max(zero, one), two); 
     if (firstZero +1 > result) 
      result = ++firstZero; 
     return result; 
    } 

    public static int negMod (int a) 
    { 
     if (a<0) 
     { 
      return (a+3); 
     } 
     return a; 
    } 

    public static int f (int[] a, int low, int high) 
    { 
     int res = 0; 
     for (int i = low; i<=high; i++) 
      res += a[i]; 
     return res; 
    } 

    public static int badWhat (int[] a) 
    { 
     int temp = 0; 
     for (int i =0; i< a.length; i++) { 
      for (int j = i; j < a.length; j++) { 
       int c = f(a, i, j); 
       if (c % 3 == 0) { 
        if (j - i + 1 > temp) 
         temp = j - i + 1; 
       } 
      } 
     } 
     return temp; 
    } 
} 

Answer 1

Одна очевидная ошибка в том, что вместо того, чтобы sumLeft += negMod(a[i] % 3); у вас есть sumLeft += negMod(a[i])%3;.

Кажется, у вас много проблем в вашем алгоритме. Прежде всего, в sumRight вы должны содержать сумму элементов от первой до текущей, но то, что вы содержали, было суммой от текущей до последней. Таким образом, было просто удачей, что ваше решение сработало для некоторых тестов.

Во-вторых, вы должны найти первый подмассив с определенным модулем и последним. Таким образом, вам не нужно перезаписывать значение после его обнаружения.

Это должно работать:

public static int what(int[] a) { 
    if (a.length == 0) { 
     return 0; 
    } 

    int sumLeft = 0, sumRight = 0; 
    for (int el : a) { 
     sumRight += el % 3; 
    } 
    sumRight = negMod(sumRight % 3); 

    int firstZero = a.length, firstOne = a.length, firstTwo = a.length, 
      lastZero = -1, lastOne = -1, lastTwo = -1; 
    for (int i = 0; i < a.length + 1; i++) { 
     if (sumLeft % 3 == 0 && firstZero == a.length) 
      firstZero = i; 
     if (sumRight % 3 == 0 && lastZero == -1) 
      lastZero = a.length - 1 - i; 
     if (sumLeft % 3 == 1 && firstOne == a.length) 
      firstOne = i; 
     if (sumRight % 3 == 1 && lastOne == -1) 
      lastOne = a.length - 1 - i; 
     if (sumLeft % 3 == 2 && firstTwo == a.length) 
      firstTwo = i; 
     if (sumRight % 3 == 2 && lastTwo == -1) 
      lastTwo = a.length - 1 - i; 
     sumLeft += negMod(a[min(i, a.length - 1)] % 3); 
     sumRight = negMod(sumRight - a[max(a.length - 1 - i, 0)] % 3); 
    } 
    int zero = lastZero - firstZero + 1; 
    int one = lastOne - firstOne + 1; 
    int two = lastTwo - firstTwo + 1; 
    Integer[] options = new Integer[]{zero, one, two, 0}; 
    return Collections.max(Arrays.asList(options)); 
}