3で割り切れる最も長いサブ配列の長さの配列をスキャンする

Question

私は配列をスキャンし、合計が3で割り切れる要素を含む最長のサブ配列の長さを生成しています。 3つのうち最大のものを返すと、それぞれの集合の差を計算して、0,1,2を与えるmodolu 3の最初と最後の合計をスキャンします。

ランダムな配列ジェネレーターを使ってテストすることにしました。それが働く時間の90％が、いくつかの数字で正解を逃している人もいます。 何が悪いと思いますか？

私は同じことをする非効率的な方法を含むテスターを含めました。画像が含まれる：

出力：

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

配列サイズは次のとおりです。17

悪い何：私は何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

1つの明らかな間違いではなくsumLeft += negMod(a[i] % 3);のあなたが持っているということですsumLeft += negMod(a[i])%3;。

アルゴリズムに多くの問題があるようです。まず最初に、sumRightには、最初から現在までの要素の合計が含まれている必要がありますが、現在のものから最後のものまでの合計です。だから、あなたのソリューションがいくつかのテストのために働いたのは幸運でした。

第2に、特定のモジュロと最後のサブアレイを持つ最初のサブアレイを見つける必要があります。したがって、値が見つかると値を上書きする必要はありません。

これは動作するはずです：

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)); 
}