Algorithm


Problem Name: 1043. Partition Array for Maximum Sum

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

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const maxSumAfterPartitioning = function(A, K) {
  const N = A.length
  const dp = new Array(N).fill(0);
  for (let i = 0; i  <  N; ++i) {
    let curMax = 0;
    for (let j = 1; j  < = K && i - j + 1 >= 0; j++) {
      curMax = Math.max(curMax, A[i - j + 1]);
      dp[i] = Math.max(dp[i], (i >= j ? dp[i - j] : 0) + curMax * j);
    }
  }
  return dp[N - 1];
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [1,15,7,9,2,5,10], k = 3

Output

x
+
cmd
84

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        N = len(A)
        dp = [0] * (N + K)
        for i in range(N):
            curMax = 0
            for k in range(1, min(K, i + 1) + 1):
                curMax = max(curMax, A[i - k + 1])
                dp[i] = max(dp[i], dp[i - k] + curMax * k)
        return dp[N - 1]
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [1,15,7,9,2,5,10], k = 3

Output

x
+
cmd
84

#3 Code Example with C# Programming

Code - C# Programming


sing System;

namespace LeetCode
{
    public class _1043_PartitionArrayForMaximumSum
    {
        public int MaxSumAfterPartitioning(int[] A, int K)
        {
            int N = A.Length;
            var dp = new int[N];
            for (int i = 0; i  <  N; i++)
            {
                var currMax = A[i];
                for (int k = 1; k  < = K && i - k + 1 >= 0; k++)
                {
                    currMax = Math.Max(currMax, A[i - k + 1]);
                    dp[i] = Math.Max(dp[i], (i >= k ? dp[i - k] : 0) + currMax * k);
                }
            }

            return dp[N - 1];
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [1], k = 1

Output

x
+
cmd
1
Advertisements

Demonstration


Previous
#1042 Leetcode Flower Planting With No Adjacent Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1044 Leetcode Longest Duplicate Substring Solution in C, C++, Java, JavaScript, Python, C# Leetcode