Problem

Given an array of numbers, find the maximum and minimum sum of sub sequences at a distance > M

Examples

Example 1:

1
2
3

Input: nums = [1, 2, 3, 4, 5], M = 2
Output: Maximum Sum = 9, Minimum Sum = 1
Explanation: For the maximum sum, the sub-sequence can be [5, 4]. For the minimum sum, the sub-sequence can be [1].

Example 2:

1
2
3

Input: nums = [10, -2, 3, 5, -7, 4], M = 1
Output: Maximum Sum = 17, Minimum Sum = -7
Explanation: For the maximum sum, the sub-sequence can be [10, 5, 4]. For the minimum sum, the sub-sequence can be [-7].

Solution

Method 1 - Recursion

Here is the approach:

  1. Recursive Function: Define a helper function dfs that computes the maximum and minimum sum for a sub-sequence ending at index i.
  2. Base Case: If i is less than 0, return negative and positive infinity respectively for the maximum and minimum sums. If i is less than or equal to M, the sums are simply the value at nums[i].
  3. Recursive Case: Recursively calculate the sums excluding and including the current element, ensuring that the elements follow the constraint of being at least M indices apart.
  4. Calculate Results: Use the helper function dfs over all indices to find the final maximum and minimum sums.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Solution {
    public int[] maxMinSumRecursive(int[] nums, int M) {
        int n = nums.length;
        Map<Integer, int[]> memo = new HashMap<>();

        int[] result = dfs(nums, n - 1, M, memo);
        return result;
    }

    private int[] dfs(int[] nums, int i, int M, Map<Integer, int[]> memo) {
        if (i < 0) {
            return new int[] {Integer.MIN_VALUE, Integer.MAX_VALUE};
        }
        if (i <= M) {
            return new int[] {nums[i], nums[i]};
        }
        if (memo.containsKey(i)) {
            return memo.get(i);
        }

        int[] result = dfs(nums, i - M - 1, M, memo);
        int max_without_i = result[0];
        int min_without_i = result[1];

        int max_with_i = Math.max(nums[i], nums[i] + max_without_i);
        int min_with_i = Math.min(nums[i], nums[i] + min_without_i);

        memo.put(i, new int[] {max_with_i, min_with_i});
        return memo.get(i);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def max_min_sum_recursive(nums, M):
    n = len(nums)

    def dfs(i, memo):
        if i < 0:
            return (float("-inf"), float("inf"))
        if i <= M:
            return (nums[i], nums[i])
        if i in memo:
            return memo[i]

        max_without_i, min_without_i = dfs(i - M - 1, memo)
        max_with_i = max(nums[i], nums[i] + max_without_i)
        min_with_i = min(nums[i], nums[i] + min_without_i)

        memo[i] = (max_with_i, min_with_i)
        return memo[i]

    max_sum, min_sum = float("-inf"), float("inf")
    memo = {}

    for i in range(n):
        mx, mn = dfs(i + M, memo)
        max_sum = max(max_sum, mx)
        min_sum = min(min_sum, mn)

    return max_sum, min_sum

Complexity

  • ⏰ Time complexity: O(2^n), due to the exponential number of calls.
  • 🧺 Space complexity: O(n), due to the recursion stack.

Method 2 - Top Down DP with memoization

Here is the approach:

  1. Memoization Table: Use a memoization table to store results of subproblems.
  2. Recursive Function with Memoization: Augment the previous recursive function to store and retrieve results from the memoization table.
  3. Avoid Redundant Calculations: Memoization ensures that each subproblem is computed only once.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class Solution {
    public int[] maxMinSumMemoized(int[] nums, int M) {
        int n = nums.length;
        Map<Integer, int[]> memo = new HashMap<>();

        int max_sum = Integer.MIN_VALUE;
        int min_sum = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int[] result = dfs(nums, i, M, memo);
            max_sum = Math.max(max_sum, result[0]);
            min_sum = Math.min(min_sum, result[1]);
        }

        return new int[] {max_sum, min_sum};
    }

    private int[] dfs(int[] nums, int i, int M, Map<Integer, int[]> memo) {
        if (i < 0) {
            return new int[] {Integer.MIN_VALUE, Integer.MAX_VALUE};
        }
        if (i <= M) {
            return new int[] {nums[i], nums[i]};
        }
        if (memo.containsKey(i)) {
            return memo.get(i);
        }

        int[] result = dfs(nums, i - M - 1, M, memo);
        int max_without_i = result[0];
        int min_without_i = result[1];

        int max_with_i = Math.max(nums[i], nums[i] + max_without_i);
        int min_with_i = Math.min(nums[i], nums[i] + min_without_i);

        memo.put(i, new int[] {max_with_i, min_with_i});
        return memo.get(i);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def max_min_sum_memoized(nums, M):
    n = len(nums)
    memo = {}

    def dfs(i):
        if i < 0:
            return (float("-inf"), float("inf"))
        if i <= M:
            return (nums[i], nums[i])
        if i in memo:
            return memo[i]
        max_without_i, min_without_i = dfs(i - M - 1)
        max_with_i = max(nums[i], nums[i] + max_without_i)
        min_with_i = min(nums[i], nums[i] + min_without_i)
        memo[i] = (max_with_i, min_with_i)
        return max_with_i, min_with_i

    max_sum, min_sum = float("-inf"), float("inf")
    for i in range(n):
        mx, mn = dfs(i)
        max_sum = max(max_sum, mx)
        min_sum = min(min_sum, mn)

    return max_sum, min_sum

Complexity

  • ⏰ Time complexity: O(n), because each subproblem is solved once and stored.
  • 🧺 Space complexity: O(n), due to the memoization table and the recursion stack.

Method 3 - Bottom up DP

Here is the approach:

  1. DP Arrays: Use two arrays max_dp and min_dp to store the maximum and minimum sums up to each index, following the constraint of being at least M indices apart.
  2. Iterative Calculation: Fill the DP arrays iteratively to ensure that constraints are respected and each sum is calculated optimally based on previous results.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class Solution {
    public int[] maxMinSumBottomUp(int[] nums, int M) {
        int n = nums.length;

        // Initialize dp arrays
        int[] max_dp = new int[n];
        int[] min_dp = new int[n];

        // Fill the DP arrays
        for (int i = 0; i < n; i++) {
            if (i <= M) {
                max_dp[i] = nums[i];
                min_dp[i] = nums[i];
            } else {
                max_dp[i] = Math.max(nums[i], nums[i] + max_dp[i - M - 1]);
                min_dp[i] = Math.min(nums[i], nums[i] + min_dp[i - M - 1]);
            }
        }

        // Find the maximum and minimum sum
        int max_sum = Integer.MIN_VALUE;
        int min_sum = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            if (max_dp[i] > max_sum)
                max_sum = max_dp[i];
            if (min_dp[i] < min_sum)
                min_sum = min_dp[i];
        }

        return new int[] {max_sum, min_sum};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def max_min_sum_bottom_up(nums, M):
    n = len(nums)

    # Initialize dp arrays
    max_dp = [0] * n
    min_dp = [0] * n

    # Fill the DP arrays
    for i in range(n):
        if i <= M:
            max_dp[i] = nums[i]
            min_dp[i] = nums[i]
        else:
            max_dp[i] = max(nums[i], nums[i] + max_dp[i - M - 1])
            min_dp[i] = min(nums[i], nums[i] + min_dp[i - M - 1])

    return max(max_dp), min(min_dp)

Complexity

  • ⏰ Time complexity: O(n), because each element is processed once.
  • 🧺 Space complexity: O(n), due to the DP arrays used for storing intermediate results.