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.
1function maxSumAfterPartitioning(arr, k) {
2 const n = arr.length;
3 const dp = Array(n + 1).fill(0);
4 for (let i = 1; i <= n; i++) {
5 let maxElem = 0, maxSum = 0;
6 for (let j = 1; j <= k && i-j >= 0; j++) {
7 maxElem = Math.max(maxElem, arr[i-j]);
8 maxSum = Math.max(maxSum, dp[i-j] + maxElem * j);
9 }
10 dp[i] = maxSum;
11 }
12 return dp[n];
13}
14
15const arr = [1, 15, 7, 9, 2, 5, 10];
16const k = 3;
17console.log(maxSumAfterPartitioning(arr, k));This JavaScript function applies dynamic programming through an array dp to capture maximum sums achievable via partitioning. Like previous solutions, for each index, it evaluates maximum partition sums through up to k potential previous elements, storing the largest results attained.
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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 private int Helper(int[] arr, int n, int k, int[] memo, int i) {
6 if (i >= n) return 0;
7 if (memo[i] != -1) return memo[i];
8 int maxElem = 0, maxSum = 0;
9 for (int j = i; j < i + k && j < n; j++) {
10 maxElem = Math.Max(maxElem, arr[j]);
11 maxSum = Math.Max(maxSum, maxElem * (j-i+1) + Helper(arr, n, k, memo, j+1));
12 }
13 return memo[i] = maxSum;
14 }
15
16 public int MaxSumAfterPartitioning(int[] arr, int k) {
17 int n = arr.Length;
18 int[] memo = new int[n];
19 Array.Fill(memo, -1);
20 return Helper(arr, n, k, memo, 0);
21 }
22
23 public static void Main(string[] args) {
24 var sol = new Solution();
25 int[] arr = {1, 15, 7, 9, 2, 5, 10};
26 int k = 3;
27 Console.WriteLine(sol.MaxSumAfterPartitioning(arr, k));
28 }
29}This C# implementation leverages recursion paired with memoization to obviate redundant computations during recursive operations. Through recursive calls, maximum segment values are computed, recorded, and recomputed with the advantage of stored memo values.