Алгоритм скользящего окна (поиск максимального числа последовательных чисел, которые складываются в определенную сумму) - PullRequest
Новая
       36

Алгоритм скользящего окна (поиск максимального числа последовательных чисел, которые складываются в определенную сумму)

0 голосов
/ 13 февраля 2019 
public class Main {
    static final int k = 0;

    public static void main(String[] args) {
        int[] arr = {1, -1, -3, 3, 7, -7, -1, -1, 10, 2};

        int startIndex = 0, endIndex = 0, currentSum = 0;
        int maxDigitsUsed = Integer.MIN_VALUE;


        while(endIndex < arr.length - 1){
            currentSum += arr[endIndex];
            if (currentSum == k && maxDigitsUsed < endIndex - startIndex) {
                maxDigitsUsed = endIndex - startIndex;
            } else {
                endIndex++;
            }
        }


        // moving the startIndex forward when there is a chance to change the sum to k
        while (startIndex <= endIndex) {
            currentSum -= arr[startIndex];
            if (currentSum == k && maxDigitsUsed < endIndex - startIndex) {
                maxDigitsUsed = endIndex - startIndex;

            }
            startIndex++;

        }
 }

Мой профессор прошел простой алгоритм скользящего окна, который проверяет максимальное количество последовательных цифр, которые складываются до указанной суммы k, в данном случае k = 0.

Однако этоне работает, когда присутствуют отрицательные числа.Почему это так и как мне это исправить?Кроме того, исходная реализация должна была быть очередью, поэтому любые ответы на основе очереди были бы очень полезны!

Эта реализация на основе массива была исключительно МОЕЙ ПОПЫТКОЙ, поэтому, пожалуйста, простите за любые вопиющие ошибки.Первоначальный вопрос включал только натуральные числа и использовал очередь вместо массива.

1 Ответ

0 голосов
/ 13 февраля 2019

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

Похоже, что ваш код делает, двигая конечный индекс вперед, пока вы не достигнете желаемой суммы, илипопал в конец массива.Затем вы перемещаете стартовый индекс вперед с теми же ограничениями.Итак, в итоге вы получите окно, которое делает это: 

[o - - - -]
[o o - - -]
[o - o - -]
[o - - o -]
[o - - - o]
[- o - - o]
[- - o - o]
[- - - o o]
[- - - - o]

Обратите внимание, что ни в каком случае ваше окно никогда не будет выглядеть так: 

[- o - o -]

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

...