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.
1import java.util.Arrays;
2
3class Solution {
4 public int maxSumAfterPartitioning(int[] arr, int k) {
5 int n = arr.length;
6 int[] dp = new int[n + 1];
7 Arrays.fill(dp, 0);
8 for (int i = 1; i <= n; i++) {
9 int maxElem = 0, maxSum = 0;
10 for (int j = 1; j <= k && i-j >= 0; j++) {
11 maxElem = Math.max(maxElem, arr[i-j]);
12 maxSum = Math.max(maxSum, dp[i-j] + maxElem * j);
13 }
14 dp[i] = maxSum;
15 }
16 return dp[n];
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 int[] arr = {1, 15, 7, 9, 2, 5, 10};
22 int k = 3;
23 System.out.println(sol.maxSumAfterPartitioning(arr, k));
24 }
25}This Java solution uses a dynamic programming strategy, similar to other languages. A dp array maintains the maximum achievable sum up to each index, considering potential partitions limited by k. The function updates dp by evaluating every possible partition point up to k, maximizing based on maximum values encountered within partitions.
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.
1#include <vector>
2#include <iostream>
3#include <climits>
4#include <cstring>
5using namespace std;
6
7class Solution {
8public:
9 int helper(vector<int>& arr, int n, int k, vector<int>& memo, int i) {
10 if (i >= n) return 0;
11 if (memo[i] != -1) return memo[i];
12 int maxElem = INT_MIN, maxSum = 0;
13 for (int j = i; j < i + k && j < n; ++j) {
14 maxElem = max(maxElem, arr[j]);
15 maxSum = max(maxSum, maxElem * (j-i+1) + helper(arr, n, k, memo, j+1));
16 }
17 return memo[i] = maxSum;
18 }
19
20 int maxSumAfterPartitioning(vector<int>& arr, int k) {
21 int n = arr.size();
22 vector<int> memo(n, -1);
23 return helper(arr, n, k, memo, 0);
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> arr = {1, 15, 7, 9, 2, 5, 10};
30 int k = 3;
31 cout << sol.maxSumAfterPartitioning(arr, k) << endl;
32 return 0;
33}This C++ program implements recursion with memoization to simplify the partitioning steps. A recursive helper function explores different partitions and optimizes through memorized data to prevent redundant computational states, thus refining performance.