Нахождение границ индекса для рекурсивной подпоследовательности - PullRequest
Новая
       26

Нахождение границ индекса для рекурсивной подпоследовательности

0 голосов
/ 05 сентября 2018

У меня есть быстрый вопрос о алгоритме максимальной подпоследовательности, который использует разделяй и властвуй, как показано ниже: 

private static int maxSum3Recursive(int[] a, int left, int right)
{ 

    if (left == right)
    {
        if (a[left] > 0)
        {

            return a[left];
        }
        else {
            return 0;
        }
    }

    int center = (left + right) / 2;
    int maxLeftSum = maxSum3Recursive(a, left, center);
    int maxRightSum = maxSum3Recursive(a, center + 1, right); 

    int maxLeftBorderSum = 0;
    int leftBorderSum = 0;
    for (int i = center; i >= left; i--)
    {
        leftBorderSum += a[i];
        if (leftBorderSum > maxLeftBorderSum)
        {
            maxLeftBorderSum = leftBorderSum;


        }
    }

    int maxRightBorderSum = 0;
    int rightBorderSum = 0;
    for (int i = center + 1; i <= right; i++)
    {
        rightBorderSum += a[i];
        if (rightBorderSum > maxRightBorderSum)
        {
            maxRightBorderSum = rightBorderSum;


        }
    }


    return Math.max(maxLeftSum, Math.max(maxRightSum, maxLeftBorderSum + maxRightBorderSum));
}

Алгоритм работает должным образом и дает мне максимальную сумму, однако у меня возникают проблемы с поиском начального и конечного индексов для границ для максимума. Например, допустим, у нас есть массив: {5, -5, 2, 9}. Сумма будет 2 + 9 = 11, а индекс будет [2 - 3], поскольку сумма должна быть последовательной. Другими словами, мы не можем просто использовать 5 и 9, чтобы получить 14, потому что они не рядом друг с другом.

Буду признателен за помощь в определении индексов.

...