Leetcode-1043. Separate arrays for maximum sum

link

1043. Separate the arrays to get the maximum and

subject

Give you an array of integers arr, Please separate the array into at most k Some of （ continuity ） Subarray . After separation , All values in each subarray will become the maximum value in that subarray .

Returns the maximum sum of elements that can be obtained after separating and transforming the array .

Be careful , The corresponding order of the original array and the separated array should be the same , in other words , You can only choose the position of the separated array, but you can't adjust the order in the array .

Example

Example 1：
Input ：arr = [1,15,7,9,2,5,10], k = 3
Output ：84
explain ：
because k=3 Can be separated into [1,15,7] [9] [2,5,10], The result is [15,15,15,9,10,10,10], And for 84, Is the largest sum of all elements of the array after separation and transformation .
If separated into [1] [15,7,9] [2,5,10], The result is [1, 15, 15, 15, 10, 10, 10] But the sum of the elements of this separation （76） Less than one . 

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

explain

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10e9
• 1 <= k <= arr.length

Ideas   Dynamic programming （DP）

We use an array dp[i] Express arr Every position in the array i  The maximum solution of the sequence composed of all previous numbers , We use K=3 For example ,dp[i] There are three situations ：

and dp[i] Is the above K The maximum value in each case , thus , We can get the state transfer equation ：

among ,, and MAX Then for To Maximum value between .

From this two-layer traversal , The first layer traverses each location , The second traversal is for k In this case , The maximum value at each position can be calculated dynamically , And the answer is the result of the last position .

C++ Code

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& A, int K) {
        // f[i] = max(f[j] + (i-j)*max(A[j..i]))

        int n = A.size();
        vector<int> f(n+1);
        for (int i = 0; i <= n; i++) {
            int curMax = 0;
            // consider past integers [j...i]
            for (int j = i-1; (i-j)<=K && j>=0; j--) {
                curMax = max(curMax, A[j]);
                f[i] = max(f[i], f[j] + (i-j)*curMax);
            }
        }
        return f[n];
    }
};