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

Question

I am attempting to find the maximum sum of non-consecutive subarrays of length at least k.

For example an array of [1, 2, 3, 1, 7, 9] with k = 2 should return 21 with subarrays [2,3] and [7,9] which are the 2 maximum subarrays and are non-consecutive (apart from one another) within the array.

Another example is [1, 2, 3, 4] k = 3 returns: 9, [2, 3, 4]

I am applying the method 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.

Can this method be altered to show the subarrays which make up the total sum?

Below are the functions described in the above method:

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

You can solve the given problem in O(n) using dynamic programming by maintaining a prefix sum array to quickly calculate the sum of a subarray of size k along with maintaining a trace array which records the action taken at each step of the array. Here's an implementation for the same: https://ideone.com/VxKzUn

The ideology behind the approach is that for every element in the array, we have an option to create our sub-array starting from this element or leave it out and move to the next element, thus giving us an optimal sub-structure the recurrence relation of which can be formulated as:

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)

The output from the above code is,

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