This approach uses dynamic programming with a one-dimensional array to find the solution. We use an array dp where dp[i] stores the maximum sum we can get for the array arr from the 0th index to the ith index. For each position, we try to partition the last k elements and update the dp array accordingly, keeping track of the maximum value observed in those elements to account for possible transformations.
Time Complexity: O(n * k) since for each index, we consider up to k previous elements.
Space Complexity: O(n) for the dp array.
1#include <stdio.h>
2#include <string.h>
3
4int maxSumAfterPartitioning(int* arr, int arrSize, int k) {
5 int dp[arrSize+1];
6 memset(dp, 0, sizeof(dp));
7 for (int i = 1; i <= arrSize; i++) {
8 int maxElem = 0, maxSum = 0;
9 for (int j = 1; j <= k && i-j >= 0; j++) {
10 maxElem = (arr[i-j] > maxElem) ? arr[i-j] : maxElem;
11 maxSum = (dp[i-j] + maxElem * j > maxSum) ? dp[i-j] + maxElem * j : maxSum;
12 }
13 dp[i] = maxSum;
14 }
15 return dp[arrSize];
16}
17
18int main() {
19 int arr[] = {1, 15, 7, 9, 2, 5, 10};
20 int k = 3;
21 int arrSize = sizeof(arr) / sizeof(arr[0]);
22 printf("%d\n", maxSumAfterPartitioning(arr, arrSize, k));
23 return 0;
24}This C program uses a dynamic programming approach with an array dp to compute the maximum sum achievable by partitioning the input array. The dp array keeps track of maximum possible sums where the loop iteratively calculates maximum sums by trying all possible partitions from 1 to k and updating dp based on the largest found values for each segment.
In this approach, a recursive function is used to solve the problem, combined with memoization to store previously computed results. The idea is to break the problem into subproblems by recursively partitioning the array from each position and recalculating sums. Alongside recursion, memoization saves time by avoiding recomputation of results for elements already processed.
Time Complexity: O(n * k), due to exponential recursive divisions curtailed by memoization.
Space Complexity: O(n) for memoization storage.
1function maxSumAfterPartitioning(arr, k) {
2 function helper(i) {
3 if (i >= arr.length) return 0;
4 if (memo[i] !== -1) return memo[i];
5 let maxElem = 0, maxSum = 0;
6 for (let j = i; j < Math.min(arr.length, i + k); j++) {
7 maxElem = Math.max(maxElem, arr[j]);
8 maxSum = Math.max(maxSum, maxElem * (j - i + 1) + helper(j + 1));
9 }
10 memo[i] = maxSum;
11 return maxSum;
12 }
13 const memo = new Array(arr.length).fill(-1);
14 return helper(0);
15}
16
17const arr = [1, 15, 7, 9, 2, 5, 10];
18const k = 3;
19console.log(maxSumAfterPartitioning(arr, k));This JavaScript function applies recursion combined with memoization to address the partitioning problem. Through sequential recursive evaluations, maximum sums are determined, remembering past results using the array memo to prevent repetitive calculations and enforce efficiency.