Найти самый длинный континуум в массиве, что сумма значений в континууме равна нулю по модулю 3

Question

Я написал код, который находит самый длинный континуум в массиве, что сумма значений в континууме равна нулю по модулю 3 , например, для массива a[]={2,-3,5,7,-20,7}

у нас есть 2-3 + 5 + 7-20 = -9 поэтому выход 5, Моя проблема сложность, теперь это O(n^3) птица шептала мне, что это может быть сделано в O(n)

public class mmn { 
public static void main(String[] args) 
{ 
    int a[]={2,-3,5,7,-20,7}; 
    int r=what(a); 
    System.out.println(r); 
} 
private 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 what(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; 
    } 

} 

Попытка переписать в О (п):

import java.util.*; 
class Main { 
public static void main (String[] args) throws Exception { 
// you should use only one Scanner object 
Scanner scanner = new Scanner(System.in); 
int a[]={3,1,3,1,3,1}; 
int n=a.length; 
int S[]=new int[n]; 
int i[]=new int[n]; 
int best; 
int sum; 

for (int j=0; j<n; j++) { 
    S[j]=a[j]%3; 
    i[j]=j;// initialize 
    //System.out.println(S[j]); 
    //System.out.println(i[j]);  
} 
best=1; 
for (int k=1; k<n; k++) { 
    if((S[k-1]+S[k])%3==0) {//checking if we want a longer continuum 
     S[k]=S[k-1]+a[k]; 
     i[k]=i[k-1]; 
    }  
    if(S[k]<S[best])//check if i should update the better 
     best=k-1; 
    } 
    System.out.println(best); 
} 
} 

Answer 1

Вот иллюстрация O(n) алгоритма в Python, что делает один проход над массивом. Идея состоит в том, что dp[i][r] представляет собой самую длинную последовательность, s, заканчивающуюся индексом i где (sum s) % 3 = r. Cleary мы ищем самые высокие dp[i][0]. Мы можем только увеличить последовательность для конкретной ячейки, если предыдущий шаг записывал любую длину для соответствующего результата по модулю. Поскольку на каждой итерации через массив мы получаем только три ячейки (константу), алгоритм имеет O(n) сложность времени и пространства. (Пространство может быть легко адаптирована к O(1), так как нам нужно только предыдущие три ячейки на каждой итерации.)

a = [2,-3,5,7,-20,7] 

best = 0 
bestIndex = -1 

dp = [[0,0,0] for i in range(len(a) + 1)] 

for i in range(1,len(a) + 1): 
    r = a[i-1] % 3 

    for j in range(3): 
    canSumToJ = dp[i-1][(3 + j - r) % 3] > 0 

    dp[i][j] = max(1 if r == j else 0 
        ,1 + dp[i-1][(3 + j - r) % 3] if canSumToJ else 0) 

    bestIndex = i - 1 if dp[i][0] > best else bestIndex 
    best = max(best,dp[i][0]) 

print(best,(bestIndex - best + 1, bestIndex)) # (5, (0, 4)) 

# dp 
# => [[0, 0, 0] 
# ,[0, 0, 1] 
# ,[1, 0, 2] 
# ,[0, 3, 2] 
# ,[3, 1, 4] 
# ,[5, 4, 2] 
# ,[3, 6, 5]] 

Answer 2

После вычисления префикса сумму с [] с использованием динамического программирования, то вы можете перебирать ы и хранить в новом массиве пары с [я]% 3 в индексе я такой, что первые индексы - это минимальные индексы, а второй - максимальные индексы, так что новый массив имеет длину 3, затем перебирает новый массив и хранит счетчик 0,1,2, наконец, снова итерации этого массива и найдем max между
(cnt [3 - moduloArray [i]] .first - i, cnt [3 - moduloArray [i]]. Секунд - i).

Answer 3

Для удовольствия:

List<List<Integer>> list = IntStream.range(0, arrayLenght).mapToObj(x -> x) 
      .flatMap(i -> IntStream.range(i, arrayLenght) 
        .mapToObj(j -> Arrays.stream(array).skip(i).limit(arrayLenght - j).mapToObj(t -> t) 
          .collect(Collectors.toList()))) 
      .collect(Collectors.toList()); 

int result = list.stream().filter(l -> l.stream().collect(Collectors.summingInt(u -> u)) % 3 == 0) 
      .max(Comparator.comparing(List::size)) 
      .map(List::size) 
      .orElse(-1); 

Это, вероятно, может быть еще больше усовершенствован, чтобы использовать немного меньше операций.

Но по крайней мере он будет работать для входов, как:

[1,3,3,3,1]