We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Partition Array for Maximum Sum

Number: 1121

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, Adobe, Bloomberg

Problem Description

Given an integer array arr and an integer k, the goal is to partition arr into contiguous subarrays such that each subarray has a length of at most k. After partitioning, every element in a subarray is replaced with the maximum value of that subarray. The task is to determine the largest possible sum of the array after performing such a partition.

Key Insights

  • This is a dynamic programming problem.
  • The optimal solution for a subarray ending at position i depends on partitions ending at previous positions.
  • For each index i, consider every possible partition length j (from 1 to k) ending at i.
  • For each possible partition, update the maximum value of the current partition and compute the candidate sum.
  • Use a DP array where dp[i] represents the maximum sum achievable for the subarray arr[0...i-1].

Space and Time Complexity

Time Complexity: O(n*k) where n is the length of the array, since we iterate over n elements and for each element we may look back up to k elements. Space Complexity: O(n) for storing the DP results.

Solution

We use a dynamic programming approach to solve the problem.

  1. Create a DP array, dp, where dp[i] represents the maximum sum achievable from the beginning of the array up to index i-1.
  2. Iterate through the array from i = 1 to n.
  3. For each position i, consider all possible subarray lengths j from 1 to k (ensuring i - j is non-negative).
  4. Within the inner loop, maintain the maximum value found in the subarray [i-j, i-1].
  5. Update dp[i] with the maximum possible value: dp[i] = max(dp[i], dp[i-j] + max_val * j) where max_val is the maximum value within the current subarray.
  6. Return dp[n] as the answer.

This method uses a two-layer iteration: the outer loop iterates over the positions in the array and the inner loop considers all possible subarrays ending at the current position, ensuring that the length of each subarray is at most k.

Code Solutions

Below are detailed code solutions in Python, JavaScript, C++, and Java.

# Define the function to partition array for maximum sum
def maxSumAfterPartitioning(arr, k):
    n = len(arr)  # Length of the input array
    dp = [0] * (n + 1)  # DP array with an extra element for ease of use

    # Iterate over each position in the array (1-indexed in dp)
    for i in range(1, n + 1):
        current_max = 0  # Initialize current maximum in the current subarray
        # Try every possible partition length up to k
        for j in range(1, min(k, i) + 1):
            # Update the current maximum with the current candidate element
            current_max = max(current_max, arr[i - j])
            # Update dp[i] to be the best sum by considering the partition ending at i with length j
            dp[i] = max(dp[i], dp[i - j] + current_max * j)
    return dp[n]

# Example test
print(maxSumAfterPartitioning([1,15,7,9,2,5,10], 3))
← Back to All Questions