n чисел расположены по кругу. Нам нужно найти максимальную сумму последовательных номеров

Question

Для линейного массива задача поиска максимальной суммы последовательных чисел. это просто. Это может быть легко сделано с помощью алгоритма Кадане., Но теперь массив находится в форме круга, и нам нужно найти максимальную сумму последовательных чисел. Таким образом, startindex и endindex могут находиться в любом месте массива. Я не понимаю, как решить это в O(n) время.

Например: { 8, 9, -14, 4, 3},

Максимальный подмассив sum= 4+3+8+9= 24. startindex=3 and endindex=1 (нулевой индексный массив). Пожалуйста, дайте мне подсказку или алгоритм о том, как подойти к этой проблеме. Код не требуется.

РЕДАКТИРОВАТЬ: Как все упоминали, круговой массив похож на тот же массив, охватывающий в два раза. Но как применить Algo Кадане к этому массиву и ограничить последовательные номера. в <=n

Answer 1

Или вместо того, чтобы скопировать массив, расширьте диапазон индексной переменной от 0..n-1 в 0..2n-1 и использовать (x mod n) вместо x в качестве индекса.

Answer 2

Скопируйте массив один раз, чтобы получить { 8, 9, -14, 4, 3, 8, 9, -14, 4, 3},

и найдите максимальный подмассив, длина которого не превышает исходный круг.

Answer 3

1. Идея состоит в том, чтобы найти максимальную сумму по алгоритму Кадане.
2. Затем найдите минимальную сумму по алгоритму Кадане, отрицая элементы, и добавьте ее к общей сумме массива.

Чем вывести максимум элементов, рассчитанных на шаге 1 и шаге 2.

private static int maxCircularSum(int a[]) {
    int max_kadane = kadane(a);
    int max_wrap = 0, i;
    for (i = 0; i < a.length; i++) {
        max_wrap += a[i]; // Calculate array-sum
        a[i] = -a[i];  // invert the array (change sign)
    }
    max_wrap = max_wrap + kadane(a);
    return (max_wrap > max_kadane) ? max_wrap : max_kadane;
}
private static int kadane(int[] a) {
    int max = Integer.MIN_VALUE, sum = 0;
    for (int k : a) {
        sum = sum + k;
        if (sum < 0) {
            sum = 0;
        }
        if (max < sum) {
            max = sum;
        }
    }
    return max;
}