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

Question

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

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

另一个例子是[1, 2, 3, 4] k = 3 returns: 9, [2, 3, 4]

我正在应用方法here which given an array of randomly sorted integers, calculates m number of subarrays of size k but does so by calculating a presum array making it difficult to identify the individual array values which make up the solution. As is done in this example。

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

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

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

您可以使用 dynamic programming 解决 O(n) 中的给定问题，方法是维护一个前缀和数组以快速计算大小为 k 的子数组的和维护一个跟踪数组，该数组记录在数组的每个步骤中采取的操作。这是相同的实现：https://ideone.com/VxKzUn

该方法背后的思想是，对于数组中的每个元素，我们都可以选择从该元素开始创建子数组，或者将其保留并移动到下一个元素，从而为我们提供最佳子数组-structure 其递归关系可以表示为：

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]]
-- * --

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

Finding array values while calculating the sum of non-consecutive subarrays of size K

java

arrays

algorithm

sliding-window

kadanes-algorithm