Рекурсивный подход «разделяй и властвуй» для получения максимальной непрерывной суммы на круговом массиве - PullRequest
Новая
       40

Рекурсивный подход «разделяй и властвуй» для получения максимальной непрерывной суммы на круговом массиве

0 голосов
/ 07 октября 2018

Я реализую подход «разделяй и властвуй» для рекурсивного решения проблемы максимальной суммы.Я получил его для обычного массива, но я изо всех сил пытаюсь реализовать его для кругового массива.

Сейчас я пытаюсь использовать модуль, чтобы просто дважды пройти массив в основном.Но это не дает мне правильных результатов, и я не уверен, почему.

Вот мой код:

Рекурсивный вызов: 

    private static int maxSubarray(int[] arr, int low, int high) {
    //base case
    if(high == low) {
        return(arr[low % arr.length]);
    } else {
        int mid = (low + high)/2;

        return Math.max(Math.max(maxSubarray(arr, low, mid), 
                maxSubarray(arr, mid+1, high)), maxCrossing(arr, low, mid, high));
    }
}

Перекрестный вызов: 

    private static int maxCrossing(int[] arr, int low, int mid, int high) {
    int leftSum = Integer.MIN_VALUE; 
    int sum = 0;
    for (int i = mid % arr.length; i >= low % arr.length; i--) {
        sum += arr[i];
        if(sum > leftSum) {
            leftSum = sum;
        }
    }
    int rightSum = Integer.MIN_VALUE; 
    sum = 0;
    for(int j = (mid + 1) % arr.length; j <= high % arr.length; j++) {
        sum += arr[j];
        if(sum > rightSum) {
            rightSum = sum;
        }
    }
    return(leftSum + rightSum);
}

Любая помощь будет признательна!Все в приведенном выше коде, которое имеет «% arr.length», отличается от реализации некруглого массива.

Кроме того, я не собираюсь реализовывать метод Кадане.

РЕДАКТИРОВАТЬ:

Забыл упомянуть, что мой начальный вызов будет maxSubarray (arr, 0, arr.length * 2 - 1) - по сути, дважды пройдя по элементам.

РЕДАКТИРОВАТЬ 2:

Здесь кое-что понял.Поскольку это задание, я подожду до истечения срока, чтобы опубликовать свое рабочее решение.

...