> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/mcm-dp-or-partition-dp/1043.-partition-array-for-maximum-sum.md).
# 1043. Partition Array for Maximum Sum
## Problem Statement
Given an integer array `arr`, partition the array into (contiguous) subarrays of length **at most** `k`. After partitioning, each subarray has their values changed to become the maximum value of that subarray.
Return *the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a **32-bit** integer.*
**Example 1:**
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]
**Example 2:**
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
**Example 3:**
Input: arr = [1], k = 1
Output: 1
**Constraints:**
* `1 <= arr.length <= 500`
* `0 <= arr[i] <= 109`
* `1 <= k <= arr.length`
## Intuition
```
Parition using front and solve for the right part
Just like Palindrome partitioning 2
```
### Links
### Video Links
### Approach 1:
```
Memoization
```
{% code title="C++" lineNumbers="true" %}
```cpp
class Solution {
public:
int find_ans(vector& arr, int k, int index, int n, vector &dp){
if(index == arr.size())
return 0;
if(dp[index] != -1)
return dp[index];
int maxi = INT_MIN;
int len = 0;
int max_sum = INT_MIN;
for(int i=index; i< min(n,index+k); i++){
len++;
maxi = max(maxi, arr[i]);
int sum = len*maxi + find_ans(arr, k, i+1, n, dp);
max_sum = max(max_sum, sum);
}
return dp[index] = max_sum;
}
int maxSumAfterPartitioning(vector& arr, int k) {
int n = arr.size();
vector dp(n, -1);
return find_ans(arr, k, 0, n, dp);
}
};
```
{% endcode %}
### Approach 2:
```
Tabulation
```
{% code title="C++" lineNumbers="true" %}
```cpp
class Solution {
public:
int maxSumAfterPartitioning(vector& arr, int k) {
int n = arr.size();
vector dp(n+1, 0);
for(int index=n-1; index>=0; index--){
int maxi = INT_MIN;
int len = 0;
int max_sum = INT_MIN;
for(int i=index; i< min(n,index+k); i++){
len++;
maxi = max(maxi, arr[i]);
int sum = len*maxi + dp[i+1];
max_sum = max(max_sum, sum);
}
dp[index] = max_sum;
}
return dp[0];
}
};
```
{% endcode %}
### Approach 3:
```
```
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Approach 4:
{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}
### Similar Problems
###