Sponsored
Sponsored
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 <vector>
2#include <algorithm>
3#include <iostream>
4using namespace std;
5
6class Solution {
7public:
8 int maxSumAfterPartitioning(vector<int>& arr, int k) {
9 int n = arr.size();
10 vector<int> dp(n+1, 0);
11 for (int i = 1; i <= n; i++) {
12 int maxElem = 0, maxSum = 0;
13 for (int j = 1; j <= k && i-j >= 0; j++) {
14 maxElem = max(maxElem, arr[i-j]);
15 maxSum = max(maxSum, dp[i-j] + maxElem * j);
16 }
17 dp[i] = maxSum;
18 }
19 return dp[n];
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> arr = {1, 15, 7, 9, 2, 5, 10};
26 int k = 3;
27 cout << sol.maxSumAfterPartitioning(arr, k) << endl;
28 return 0;
29}This C++ program leverages the dynamic programming technique with a vector dp to store the maximum possible sums. It iteratively computes by evaluating each potential cutoff position within the last k elements to determine the best partition sums.
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.
In this C solution, a recursive function named helper is used to evaluate possible partitions lazily. The use of memoization, through an integer array memo, optimizes this by caching previously calculated subproblem results. This active arrangement ensures computative processes reuse stored values during recursion.