在计算大小为 K 的非连续子数组的总和时查找数组值

Question

我试图找到长度至少为 k 的非连续子数组的最大和。

例如，一个 [1, 2, 3, 1, 7, 9] 数组，k = 2 应该返回 21 子数组 [2,3] 和 [7,9]，它们是 2 个最大子数组并且是不连续的（彼此分开）在阵列中。

另一个例子是 [1, 2, 3, 4] k = 3 返回： 9, [2, 3, 4]

我在这里应用的方法给出了一个随机排序的整数数组，计算了 m 个大小为 k 的子数组，但通过计算一个假定数组来实现，这使得很难识别构成解决方案的各个数组值。正如本例中所做的那样。

可以更改此方法以显示构成总和的子数组吗？

以下是上述方法中描述的功能：

// 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;

    }

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 defaultdictdp = defaultdict(lambda: -1)prefixsum = []trace = []def getSubArraySum(i, j):&nbsp; &nbsp; if i == 0:&nbsp; &nbsp; &nbsp; &nbsp; return prefixsum[j]&nbsp; &nbsp; return (prefixsum[j] - prefixsum[i - 1])def rec(cur, arr, k):&nbsp; &nbsp; if cur >= len(arr):&nbsp; &nbsp; &nbsp; &nbsp; return 0&nbsp; &nbsp; if dp[cur] != -1:&nbsp; &nbsp; &nbsp; &nbsp; return dp[cur]&nbsp; &nbsp; # Assuming that all the elements in the array is positive,&nbsp;&nbsp; &nbsp; # else set s1 and s2 to -Infinity&nbsp; &nbsp; s1 = -1; s2 = -1&nbsp; &nbsp; # If we choose the subarray starting at `cur`&nbsp; &nbsp; if cur + k - 1 < len(arr):&nbsp; &nbsp; &nbsp; &nbsp; s1 = getSubArraySum(cur, cur + k - 1) + rec(cur + k + 1, arr, k)&nbsp; &nbsp; # If we ignore the subarray starting at `cur`&nbsp; &nbsp; s2 = rec(cur + 1, arr, k)&nbsp; &nbsp; dp[cur] = max(s1, s2)&nbsp; &nbsp; if s1 >= s2:&nbsp; &nbsp; &nbsp; &nbsp; trace[cur] = (True, cur + k + 1)&nbsp; &nbsp; &nbsp; &nbsp; return s1&nbsp; &nbsp; trace[cur] = (False, cur + 1)&nbsp; &nbsp; return s2def getTrace(arr, trace, k):&nbsp; &nbsp; itr = 0&nbsp; &nbsp; subArrays = []&nbsp; &nbsp; while itr < len(trace):&nbsp; &nbsp; &nbsp; &nbsp; if trace[itr][0]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; subArrays.append(arr[itr : itr + k])&nbsp; &nbsp; &nbsp; &nbsp; itr = trace[itr][1]&nbsp; &nbsp; return subArraysdef solve(arr, k):&nbsp; &nbsp; global dp, trace, prefixsum&nbsp; &nbsp; dp = defaultdict(lambda: -1)&nbsp; &nbsp; trace = [(False, 0)] * len(arr)&nbsp; &nbsp; prefixsum = [0] * len(arr)&nbsp; &nbsp; prefixsum[0] = arr[0]&nbsp; &nbsp; for i in range(1, len(arr)):&nbsp; &nbsp; &nbsp; &nbsp; prefixsum[i] += prefixsum[i - 1] + arr[i]&nbsp; &nbsp; print("Array :", arr)&nbsp; &nbsp; print("Max sum: ", rec(0, arr, k))&nbsp; &nbsp; print("Subarrays: ", getTrace(arr, trace, k))&nbsp; &nbsp; print("-- * --")solve([1, 2, 3, 4], 3)solve([1, 2, 3, 1, 7, 9] , 2)上面代码的输出是，Array : [1, 2, 3, 4]Max sum:&nbsp; 9Subarrays:&nbsp; [[2, 3, 4]]-- * --Array : [1, 2, 3, 1, 7, 9]Max sum:&nbsp; 21Subarrays:&nbsp; [[2, 3], [7, 9]]-- * --