为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

白猪掌柜的 2021-11-24 16:17:21
我试图找到长度至少为 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 arraypublic 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;    }
查看完整描述

1 回答

?
德玛西亚99

TA贡献1770条经验 获得超3个赞

可以解决在给定的问题为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]]

-- * --


查看完整回答
反对 回复 2021-11-24
  • 1 回答
  • 0 关注
  • 188 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信