Нахождение значений массива при расчете суммы непоследовательных подмассивов размера K

Question

Я пытаюсь найти максимальную сумму непоследовательных подмассивов длиной не менее k.

Например, массив [1, 2, 3, 1, 7, 9] с k = 2должен возвращать 21 с подмассивами [2,3] и [7,9], которые являются двумя максимальными подмассивами и не являются последовательными (отдельно друг от друга) в массиве.

Другой пример - [1, 2, 3, 4] k = 3 возвращает: 9, [2, 3, 4]

Я применяю метод здесь , который дает массив случайно отсортированных целых чисел, вычисляет число mподмассивы размера k, но это делается путем вычисления массива presum, что затрудняет идентификацию отдельных значений массива, составляющих решение.Как это сделано в этом примере .

Можно ли изменить этот метод, чтобы показать подмассивы, составляющие общую сумму?

Ниже приведены функции, описанные в вышеприведенном методе:

// reorganize array
public static int calcProfit(List<Integer> inputArray){
    int lotCount = inputArray.get(0);
    inputArray.remove(0);
    int maxBusiness = inputArray.get(0);
    inputArray.remove(0);

    // convert arrayList to int array
    int[] workingArray = new int[inputArray.size()];

    for(int i = 0; i < inputArray.size(); i++) {
        if (inputArray.get(i) != null) {
            workingArray[i] = inputArray.get(i);
        }
    }

    System.out.println(Arrays.toString(workingArray));

    int prefixArray[] = new int[lotCount + 1 - maxBusiness];

    int maxArrays = (int) Math.ceil(lotCount / maxBusiness);


    arraySum(prefixArray, workingArray, lotCount, maxBusiness);

    System.out.println("Prefix array is" + Arrays.toString(prefixArray));

    int completeArray = maxSubarray(prefixArray, maxArrays, lotCount + 1 - maxBusiness, maxBusiness, 0);

    return completeArray;
}


static void arraySum(int presum[], int arr[], int n, int k)
{
    for (int i = 0; i < k; i++)
        presum[0] += arr[i];

    // store sum of array index i to i+k
    // in presum array at index i of it.
    for (int i = 1; i <= n - k; i++)
        presum[i] += presum[i - 1] + arr[i + k - 1] -
                arr[i - 1];
}

private static int maxSubarray(int preSum[], int m, int size, int k, int start) {

    // stop if array length is 0
    if (m == 0) {
        return 0;
    }

    // stop if start greater than preSum
    if (start > size - 1) {
        return 0;
    }

    System.out.println("m is : " + m + " start is : " + start);

    // if including subarray of size k
    int includeMax = preSum[start] + maxSubarray(preSum,m - 1, size, k, start + k);

    // search next possible subarray
    int excludeMax = maxSubarray(preSum, m, size, k, start + 1);

    System.out.println("exclude max is : " + excludeMax + " include max is " + includeMax);
    // return max
    return Math.max(includeMax, excludeMax);

}

Answer 1

Вы можете решить данную проблему в O (n) , используя dynamic programming, поддерживая массив префиксных сумм, чтобы быстро вычислить сумму подмассива размера k, а также поддерживая массив трасс, который записываетдействие, предпринимаемое на каждом шаге массива.Вот реализация для того же: https://ideone.com/VxKzUn

Идеология, лежащая в основе этого подхода, заключается в том, что для каждого элемента в массиве у нас есть возможность создать наш подмассив, начиная с этого элемента, или оставить его и переместитьк следующему элементу, таким образом, давая нам оптимальную подструктуру, отношение рекуррентности которой можно сформулировать как:

f(n) = max{ sum(arr[n], .. , arr[n + k]) + f(n + k + 1), f(n + 1) }

from collections import defaultdict

dp = defaultdict(lambda: -1)
prefixsum = []
trace = []

def getSubArraySum(i, j):
    if i == 0:
        return prefixsum[j]
    return (prefixsum[j] - prefixsum[i - 1])

def rec(cur, arr, k):
    if cur >= len(arr):
        return 0
    if dp[cur] != -1:
        return dp[cur]

    # Assuming that all the elements in the array is positive, 
    # else set s1 and s2 to -Infinity
    s1 = -1; s2 = -1

    # If we choose the subarray starting at `cur`
    if cur + k - 1 < len(arr):
        s1 = getSubArraySum(cur, cur + k - 1) + rec(cur + k + 1, arr, k)
    # If we ignore the subarray starting at `cur`
    s2 = rec(cur + 1, arr, k)

    dp[cur] = max(s1, s2)

    if s1 >= s2:
        trace[cur] = (True, cur + k + 1)
        return s1
    trace[cur] = (False, cur + 1)
    return s2

def getTrace(arr, trace, k):
    itr = 0
    subArrays = []
    while itr < len(trace):
        if trace[itr][0]:
            subArrays.append(arr[itr : itr + k])
        itr = trace[itr][1]
    return subArrays

def solve(arr, k):
    global dp, trace, prefixsum

    dp = defaultdict(lambda: -1)
    trace = [(False, 0)] * len(arr)
    prefixsum = [0] * len(arr)

    prefixsum[0] = arr[0]
    for i in range(1, len(arr)):
        prefixsum[i] += prefixsum[i - 1] + arr[i]

    print("Array :", arr)
    print("Max sum: ", rec(0, arr, k))
    print("Subarrays: ", getTrace(arr, trace, k))
    print("-- * --")

solve([1, 2, 3, 4], 3)
solve([1, 2, 3, 1, 7, 9] , 2)

Выход изкод выше,

Array : [1, 2, 3, 4]
Max sum:  9
Subarrays:  [[2, 3, 4]]
-- * --
Array : [1, 2, 3, 1, 7, 9]
Max sum:  21
Subarrays:  [[2, 3], [7, 9]]
-- * --