💡 Problem Formulation: The task is to find out the largest sum of a subsequence from a given list of integers, where the sum is divisible by a given integer k. For example, given the list [3, 1, 4, 2, 2] and k = 3, one of the subsequences with the largest sum divisible by k is [3, 4, 2], with a sum of 9.
Method 1: Dynamic Programming
Dynamic programming can be used to solve this problem by keeping track of the remainder of the sum of subsequences modulo k. We start by initializing an array to keep track of maximum sums with remainder i after looking at each element of the input array. We update this array as we iterate through the input, and eventually, the largest divisible subsequence sum is found.
Here’s an example:
def largest_k_divisible_subseq_sum(arr, k):
dp = [-1] * k
dp[0] = 0
for number in arr:
temp = dp[:] # Copy the current state of dp
for i in range(k):
if dp[i] >= 0:
temp[(i + number) % k] = max(dp[(i + number) % k], dp[i] + number)
dp = temp
return dp[0]
print(largest_k_divisible_subseq_sum([3, 1, 4, 2, 2], 3))
Output: 9
This code snippet defines a function largest_k_divisible_subseq_sum, which computes the largest sum of a subsequence divisible by k. The function uses a list, dp, to store the maximum sums for each remainder when divided by k. We loop through each number and update the dp table. The final answer is the maximum sum corresponding to a remainder of 0.
Method 2: Recursive Brute Force
The brute force approach explores all possible subsequences and checks if the sum is divisible by k. Although not efficient, it serves as a straightforward way to understand the problem. It relies on recursion to explore all possibilities, returning the maximum sum that satisfies the divisibility condition.
Here’s an example:
def max_divisible_subseq_sum(arr, k, index=0, current_sum=0):
if index == len(arr):
return current_sum if current_sum % k == 0 else 0
include = max_divisible_subseq_sum(arr, k, index + 1, current_sum + arr[index])
exclude = max_divisible_subseq_sum(arr, k, index + 1, current_sum)
return max(include, exclude)
print(max_divisible_subseq_sum([3, 1, 4, 2, 2], 3))
Output: 9
This recursive function max_divisible_subseq_sum explores every subsequence of the input array. It considers two scenarios for each element: including it in the sum or excluding it, using a helper function with parameters for the current index and the current running sum. The base case returns the running sum if it’s divisible by k, and 0 otherwise. The final output is the maximum sum found that is divisible by k.
Method 3: Iterative Subset Sum
Another method involves using bit manipulation to generate all subsets iteratively. This method examines each subset’s sum and retains the maximum sum divisible by k. Although more efficient than the recursive brute force, it may still be impractical for large input arrays.
Here’s an example:
def max_k_divisible_subset_sum(arr, k):
n = len(arr)
max_sum = 0
for i in range(1 < < n):
subset_sum = sum(arr[j] for j in range(n) if i & (1 < < j))
if subset_sum % k == 0:
max_sum = max(max_sum, subset_sum)
return max_sum
print(max_k_divisible_subset_sum([3, 1, 4, 2, 2], 3))
Output: 9
The function max_k_divisible_subset_sum creates all possible subsets using a binary representation of numbers and the bitwise AND operation. It calculates the sum of each subset and if the sum is divisible by k, it updates the max_sum if necessary.
Method 4: Memoization
Memoization improves upon the recursive brute force approach by storing the results of sub-problems. The recursive function is modified to accept and utilize a memoization table that prevents recalculating the sum for the same subsequence.
Here’s an example:
def max_divisible_sum_memo(arr, k, index=0, current_sum=0, memo=None):
if memo is None:
memo = {}
if (index, current_sum) in memo:
return memo[(index, current_sum)]
if index == len(arr):
return current_sum if current_sum % k == 0 else 0
include = max_divisible_sum_memo(arr, k, index + 1, current_sum + arr[index], memo)
exclude = max_divisible_sum_memo(arr, k, index + 1, current_sum, memo)
memo[(index, current_sum)] = max(include, exclude)
return memo[(index, current_sum)]
print(max_divisible_sum_memo([3, 1, 4, 2, 2], 3))
Output: 9
This version of the function max_divisible_sum_memo uses a dictionary memo to store already computed sums. This reduces the number of redundant computations significantly and improves the performance when compared to the non-memoized version.
Bonus One-Liner Method 5: Combinatorics with itertools
Utilizing Python’s itertools module, one can write a one-liner to generate all subsets and compute the maximum k divisible sum. This method is concise but not recommended for large arrays due to its inefficiency.
Here’s an example:
from itertools import combinations
def max_k_divisible_by_itertools(arr, k):
return max((sum(sub) for i in range(len(arr)+1) for sub in combinations(arr, i) if sum(sub) % k == 0), default=0)
print(max_k_divisible_by_itertools([3, 1, 4, 2, 2], 3))
Output: 9
This one-liner uses a generator expression within the max function to iterate over all possible combinations of different sizes, checking each for divisibility by k and calculating their sums, returning the maximum.
Summary/Discussion
- Method 1: Dynamic Programming. Efficient for medium-sized arrays. Complexity can be high for large values of
k. Optimal solution. - Method 2: Recursive Brute Force. Easy to understand. Extremely slow for large arrays, exponential time complexity.
- Method 3: Iterative Subset Sum. Faster than brute force. Time complexity is still exponential, which can be a bottleneck for large arrays.
- Method 4: Memoization. Significant performance improvement over brute force. Complexity may still be high for large input arrays but works well for medium-sized inputs.
- Bonus Method 5: Combinatorics with itertools. Very concise. Only practical for extremely small arrays due to inefficiency.